基础内容知识,来自维基百科

算法。

定义

算法algorithm),在数学算学)和计算机科学之中,为任何良定义的具体计算步骤的一个序列[1],常用于计算数据处理自动推理。精确而言,算法是一个表示为有限长[2]列表的有效方法。算法应包含清晰定义的指令[3]用于计算函数[4]

个人理解:通过计算解决问题的方法。

基本要素

常用设计模式[编辑]

完全遍历法和不完全遍历法:在问题的解是有限离散解空间,且可以验证正确性和最优性时,最简单的算法就是把解空间的所有元素完全遍历一遍,逐个检测元素是否是我们要的解。这是最直接的算法,实现往往最简单。但是当解空间特别庞大时,这种算法很可能导致工程上无法承受的计算量。这时候可以利用不完全遍历方法——例如各种搜索法和规划法——来减少计算量。

分治法:把一个问题分区成互相独立的多个部分分别求解的思路。这种求解思路带来的好处之一是便于进行并行计算。

动态规划法:当问题的整体最优解就是由局部最优解组成的时候,经常采用的一种方法。

贪婪算法:常见的近似求解思路。当问题的整体最优解不是(或无法证明是)由局部最优解组成,且对解的最优性没有要求的时候,可以采用的一种方法。

线性规划法:见条目。

简并法:把一个问题通过逻辑或数学推理,简化成与之等价或者近似的、相对简单的模型,进而求解的方法。

常用实现方法[编辑]

递归方法迭代方法

顺序计算、并行计算分布式计算:顺序计算就是把形式化算法用编程语言进行单线程序列化后执行。

确定性算法和非确定性算法

精确求解和近似求解

复杂度

时间复杂度[编辑]

算法的时间复杂度是指算法需要消耗的时间资源。一般来说,计算机算法是问题规模n的函数f(n),算法的时间复杂度也因此记做

T(n)=O(f(n))

算法执行时间的增长率与f(n)的增长率正相关,称作渐近时间复杂度,简称时间复杂度。

常见的时间复杂度有:常数阶O(1),对数阶O(log⁡n),线性阶O(n),线性对数阶O(nlog⁡n),平方阶O(n2),立方阶O(n3),…,k次方阶O(nk),指数阶O(2n)。随着问题规模n的不断增大,上述时间复杂度不断增大,算法的执行效率越低。

空间复杂度[编辑]

算法的空间复杂度是指算法需要消耗的空间资源。其计算和表示方法与时间复杂度类似,一般都用复杂度的渐近性来表示。同时间复杂度相比,空间复杂度的分析要简单得多。

个人理解,时间复杂度,空间复杂度。

主要看时间复杂度,也就是说。算法运算需要的时间。常数,对数,线性,线性对数,平方,立方,N次方,指数(爆炸的时间消耗)。

示例[编辑]

求最大值算法[编辑]

1.冒泡

求最大公约数算法[编辑]

求两个自然数的最大公约数 设两个变量MN

  1. 如果M<N,则交换MN
  2. MN除,得到余数R
  3. 判断R=0,正确则N即为“最大公约数”,否则下一步
  4. N赋值给M,将R赋值给N,重做第一步。

ANSI C代码表示

//交換2數
void swapi(int *x, int *y)
{
  int tmp = *x;
  *x = *y;
  *y = tmp;
}

int gcd(int m, int n)
{
  int r;
  do
  {
    if (m < n)
      swapi(&m, &n);
    r = m % n;
    m = n;
    n = r;
  } while (r);
  return m;
}

利用if函数以及递归则能做出更为精简的代码,更可省去交换的麻烦。(但是也因为递归调用,其空间复杂度提高)

int gcd(int a,int b)
{
    if(a%b)
        return gcd(b,a%b);
    return b;
}

发表评论

邮箱地址不会被公开。