算法和算法分析

本文最后更新于:4 个月前

算法和算法分析

算法的定义和特性

算法(Algorithm)是为了解决某类问题而规定的有限长的操作序列。

  1. 有穷性

    算法总是在执行有穷步后结束,每一步都会在有穷时间内完成;

  2. 确定性

    对于每种情况下对应的操作,在算法中都有确切的规定,不会产生二义性;

  3. 可行性

    算法中所有操作都可以通过已经实现的基本操作运算有限次数来实现;

  4. 输入

    一个算法有零个或多个输入;

  5. 输出

  6. 一个算法有一个或多个输出;

评价算法优劣的基本标准
  1. 正确性

    在合理数据的输入下,能在有效的时间内得到正确的结果

  2. 可读性

    一个好的算法,首先应便于人们理解和相互交流 , 其次才是机器可执行性。

    可读性强的算法有助于人们对算法的理解,而难懂的算法容易隐藏错误,且难于调试和修改。

  3. 壮健性

    当输入的数据非法时,好的算法能适当地做出正确反应或进行相应处理,而不会产生一些莫名其妙的输出结果。

  4. 高效性

    高效性包括时间和空间两个方面。

    时间高效是指算法设计合理,执行效率高,可以用时间复杂度来度量;

    空间高效是指算法占用存储容量合理,可以用空间复杂度来度量。


算法的时间复杂度

算法效率分析的目的是看算法实际是否可行;同一问题存在多个算法时,可进行时间和空间性能上的比较,以便从中挑选出较优算法。

衡量算法效率的方法主要是两大类:事后统计法和事前统计法.

⚠️:事后统计法需要先将算法实现,然后测算其时间和空间开销。这种方法的缺陷很显然,一是必须把算法转换成可执行的程序,二是时空开销的测算结果依赖于计算机的软硬件等环境因素,这容易掩盖算法本身的优劣。

问题规模和语句频度

不考虑计算机硬件等因素,影响算法时间代价的主要因素是问题规模。问题规模是算法求解问题中的输入量大小,是问题大小的本质;一般用整数n表示。

一条语句的重复执行次数称作语句频度。语句执行一次所需要的时间要根据计算机软件,硬件相关,所以算法不是精确执行时间。

一个算法执行时间大致上等于所有语句执行时间总和,而语句的执行时间则为该条语句的重复次数和执行一次所需时间的乘积.

1
2
3
4
5
6
7
8
for (let i = 1; i<= n; i++) {   // 频度为 n+1(初始值为1,循环n次,还要走一次条件判断是否继续循环, 所以是n+1)
for (let j = 1; j<=n; j++) { // 频度是 n * (n+1), 最后一次外层判断进不来所以是n次,乘以外层的n*(n+1)
c[i][j] = 0 ; // 频度为n^2, 两个for循环的有效次
for (k = 1;k <= n; k++ ) // 频度为n^2 * (n+1)
c[i][j] = c[i][j] + a[i] [k]*b[k] [j]; // 频度为n^3
}
}
// 上述的执行时间f(n) = 2n^3 + 3n^2 + 2n + 1
算法的时间复杂度定义

为了客观的反映一个算法的执行时间,可以只用算法中的“基本语句”的执行次数来衡量算法的工作量。

所谓“基本语句”,指的是算法中重复执行次数和苏那份的执行时间成正比的语句。

定理1.1:

​ 若f(n) = an^m + bn^(m-1) + an + a 是一个m次的多项式,则T(n) = O(n^m)

​ 我们可以忽略掉所有的低次幂和最高次幂的系数

1
2
// 当两条语句的频度均是1,算法的执行时间与问题规模n无关的常数,所以T(n) = O(1),称为常量阶。
x++;s-0;
1
2
3
// 循环体内的两个语句频度均为f(n) = n, 所以算法时间复杂度是T(n) = O(n),称为线性阶。
// 对于循环语句只考虑循环体内的执行次数,当存在for循环双层嵌套的时候,时间复杂度为T(n) = O(n^2),由此类推。
for(i = 0; i<n; i++) {x++;s=0;}

算法的空间复杂度

对于算法的存储空间,类似于算法的时间复杂度, 采用渐进空间复杂度.

当我们知道既然时间复杂度不是用来计算程序具体耗时的,那么我也应该明白,空间复杂度也不是用来计算程序实际占用的空间的。

  1. 空间复杂度 O(1)

如果算法执行所需要的临时空间不随着某个变量n的大小而变化,即此算法空间复杂度为一个常量,可表示为 O(1)

  1. 空间复杂度 O(n)

如果存在开辟显得空间,比如int[] m = new int[n],这段代码的空间复杂度即 S(n) = O(n)