为什么要进行算法分析?
如何衡量算法复杂度?
算法的运行时间与什么相关?
算法分析的种类:
例如,在一个长度为 n 的列表中顺序搜索指定的值,则
而实际中,我们一般仅考量算法在最坏情况下的运行情况,也就是对于规模为 n 的任何输入,算法的最长运行时间。这样做的理由是:
1、一个算法的最坏情况运行时间是在任何输入下运行时间的一个上界(Upper Bound)。
2、对于某些算法,最坏情况出现的较为频繁。
3、大体上看,平均情况通常与最坏情况一样差。
算法分析要保持大局观(Big Idea),其基本思路:
1、忽略掉那些依赖于机器的常量。
2、关注运行时间的增长趋势。
比如:T(n) = 73n3 + 29n3 + 8888 的趋势就相当于 T(n) = Θ(n3)。
渐近记号(Asymptotic Notation)通常有 O、 Θ 和 Ω 记号法。Θ 记号渐进地给出了一个函数的上界和下界,当只有渐近上界时使用 O 记号,当只有渐近下界时使用 Ω 记号。尽管技术上 Θ 记号较为准确,但通常仍然使用 O 记号表示。
使用 O 记号法(Big O Notation)表示最坏运行情况的上界。例如,
例如:
相当于:
注1:快速的数学回忆,logab = y 其实就是 ay = b。所以,log24 = 2,因为
22 = 4。同样 log28 = 3,因为 23 = 8。我们说,log2n 的增长速度要慢于 n,因为当 n = 8 时,log2n = 3。
注2:通常将以 10 为底的对数叫做常用对数。为了简便,N 的常用对数 log10 N 简写做 lg N,例如 log10 5 记做 lg 5。
注3:通常将以无理数 e 为底的对数叫做自然对数。为了方便,N 的自然对数 loge N 简写做 ln N,例如 loge 3 记做 ln 3。
注4:在算法导论中,采用记号 lg n = log2 n ,也就是以 2 为底的对数。改变一个对数的底只是把对数的值改变了一个常数倍,所以当不在意这些常数因子时,我们将经常采用 "lg n"记号,就像使用 O 记号一样。计算机工作者常常认为对数的底取 2 最自然,因为很多算法和数据结构都涉及到对问题进行二分。
而通常时间复杂度与运行时间有一些常见的比例关系:
计算代码块的渐进运行时间的方法有如下步骤:
1、确定决定算法运行时间的组成步骤。
2、找到执行该步骤的代码,标记为 1。
3、查看标记为 1 的代码的下一行代码。如果下一行代码是一个循环,则将标记 修改为 1 倍于循环的次数 1 * n。如果包含多个嵌套的循环,则将继续计算倍数,例如 1 * n * m。
4、找到标记到的最大的值,就是运行时间的最大值,即算法复杂度描述的上界。
示例代码(1):
decimal Factorial(int n) { if (n == 0) return 1; else return n * Factorial(n - 1); }
阶乘(factorial),给定规模 n,算法基本步骤执行的数量为 n,所以算法复杂度为 O(n)。
示例代码(2):
int FindMaxElement(int[] array) { int max = array[0]; for (int i = 0; i < array.Length; i++) { if (array[i] > max) { max = array[i]; } } return max; }
这里,n 为数组 array 的大小,则最坏情况下需要比较 n 次以得到最大值,所以算法复杂度为 O(n)。
示例代码(3):
long FindInversions(int[] array) { long inversions = 0; for (int i = 0; i < array.Length; i++) for (int j = i + 1; j < array.Length; j++) if (array[i] > array[j]) inversions++; return inversions; }
这里,n 为数组 array 的大小,则基本步骤的执行数量约为 n*(n-1)/2,所以算法复杂度为 O(n2)。
示例代码(4):
long SumMN(int n, int m) { long sum = 0; for (int x = 0; x < n; x++) for (int y = 0; y < m; y++) sum += x * y; return sum; }
给定规模 n 和 m,则基本步骤的执行数量为 n*m,所以算法复杂度为 O(n2)。
示例代码(5):
decimal Sum3(int n) { decimal sum = 0; for (int a = 0; a < n; a++) for (int b = 0; b < n; b++) for (int c = 0; c < n; c++) sum += a * b * c; return sum; }
这里,给定规模 n,则基本步骤的执行数量约为 n*n*n ,所以算法复杂度为 O(n3)。
示例代码(6):
decimal Calculation(int n) { decimal result = 0; for (int i = 0; i < (1 << n); i++) result += i; return result; }
这里,给定规模 n,则基本步骤的执行数量为 2n,所以算法复杂度为 O(2n)。
示例代码(7):
斐波那契数列:
Fib(0) = 0 Fib(1) = 1 Fib(n) = Fib(n-1) + Fib(n-2) F() = 0, 1, 1, 2, 3, 5, 8, 13, 21, 34 ...
int Fibonacci(int n) { if (n <= 1) return n; else return Fibonacci(n - 1) + Fibonacci(n - 2); }
这里,给定规模 n,计算 Fib(n) 所需的时间为计算 Fib(n-1) 的时间和计算 Fib(n-2) 的时间的和。
T(n<=1) = O(1)
T(n) = T(n-1) + T(n-2) + O(1)
fib(5)
/ \
fib(4) fib(3)
/ \ / \
fib(3) fib(2) fib(2) fib(1)
/ \ / \ / \
通过使用递归树的结构描述可知算法复杂度为 O(2n)。
示例代码(8):
int Fibonacci(int n) { if (n <= 1) return n; else { int[] f = new int[n + 1]; f[0] = 0; f[1] = 1; for (int i = 2; i <= n; i++) { f[i] = f[i - 1] + f[i - 2]; } return f[n]; } }
同样是斐波那契数列,我们使用数组 f 来存储计算结果,这样算法复杂度优化为 O(n)。
示例代码(9):
int Fibonacci(int n) { if (n <= 1) return n; else { int iter1 = 0; int iter2 = 1; int f = 0; for (int i = 2; i <= n; i++) { f = iter1 + iter2; iter1 = iter2; iter2 = f; } return f; } }
同样是斐波那契数列,由于实际只有前两个计算结果有用,我们可以使用中间变量来存储,这样就不用创建数组以节省空间。同样算法复杂度优化为 O(n)。
示例代码(10):
通过使用矩阵乘方的算法来优化斐波那契数列算法。
static int Fibonacci(int n) { if (n <= 1) return n; int[,] f = { { 1, 1 }, { 1, 0 } }; Power(f, n - 1); return f[0, 0]; } static void Power(int[,] f, int n) { if (n <= 1) return; int[,] m = { { 1, 1 }, { 1, 0 } }; Power(f, n / 2); Multiply(f, f); if (n % 2 != 0) Multiply(f, m); } static void Multiply(int[,] f, int[,] m) { int x = f[0, 0] * m[0, 0] + f[0, 1] * m[1, 0]; int y = f[0, 0] * m[0, 1] + f[0, 1] * m[1, 1]; int z = f[1, 0] * m[0, 0] + f[1, 1] * m[1, 0]; int w = f[1, 0] * m[0, 1] + f[1, 1] * m[1, 1]; f[0, 0] = x; f[0, 1] = y; f[1, 0] = z; f[1, 1] = w; }
优化之后算法复杂度为O(log2n)。
示例代码(11):
在 C# 中更简洁的代码如下。
static double Fibonacci(int n) { double sqrt5 = Math.Sqrt(5); double phi = (1 + sqrt5) / 2.0; double fn = (Math.Pow(phi, n) - Math.Pow(1 - phi, n)) / sqrt5; return fn; }
示例代码(12):
插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中,从而得到一个新的有序数据。算法适用于少量数据的排序,时间复杂度为 O(n2)。
private static void InsertionSortInPlace(int[] unsorted) { for (int i = 1; i < unsorted.Length; i++) { if (unsorted[i - 1] > unsorted[i]) { int key = unsorted[i]; int j = i; while (j > 0 && unsorted[j - 1] > key) { unsorted[j] = unsorted[j - 1]; j--; } unsorted[j] = key; } } }
本文分享自 交互设计前端开发与后端程序设计 微信公众号,前往查看
如有侵权,请联系 cloudcommunity@tencent.com 删除。
本文参与 腾讯云自媒体同步曝光计划 ,欢迎热爱写作的你一起参与!