用这篇博客记录一下学习如何计算时间复杂度的过程. 本文会从时间复杂度的定义到具体案例的练习, 让初学者对时间复杂度有个基本印象.
摘自《维基百科》
在计算机科学中, 算法 https://zh.wikipedia.org/wiki/算法 的时间复杂度是一个函数 https://zh.wikipedia.org/wiki/函数 , 它定性描述该算法的运行时间. 这是一个代表算法输入值的字符串的长度的函数. 时间复杂度常用大 O 符号表述, 不包括这个函数的低阶项和首项系数. 使用这种方式时, 时间复杂度可被称为是渐近的, 亦即考察输入值大小趋近无穷时的情况. 例如, 如果一个算法对于任何大小为 n (必须比 n0 大)的输入, 它至多需要 5n3 + 3n 的时间运行完毕, 那么它的渐近时间复杂度是 O(n3).
为了计算时间复杂度, 我们通常会估计算法的操作单元数量, 每个单元运行的时间都是相同的. 因此, 总运行时间和算法的操作单元数量最多相差一个常量系数.
相同大小的不同输入值仍可能造成算法的运行时间不同, 因此我们通常使用算法的最坏情况复杂度, 记为 T(n) , 定义为任何大小的输入 n 所需的最大运行时间.
摘自《百度百科》
1. 一般情况下, 算法中基本操作重复执行的次数是问题规模 n 的某个函数, 用 T(n)表示, 若有某个辅助函数 f(n), 使得 T(n)/f(n)的极限值 (当 n 趋近于无穷大时) 为不等于零的常数, 则称 f(n)是 T(n)的同数量级函数. 记作 T(n)=O(f(n)), 称 O(f(n)) 为算法的渐进时间复杂度, 简称时间复杂度.
分析: 随着模块 n 的增大, 算法执行的时间的增长率和 f(n) 的增长率成正比, 所以 f(n) 越小, 算法的时间复杂度越低, 算法的效率越高.
2. 在计算时间复杂度的时候, 先找出算法的基本操作, 然后根据相应的各语句确定它的执行次数, 再找出 T(n) 的同数量级(它的同数量级有以下: 1,log2n,n,n log2n ,n 的平方, n 的三次方, 2 的 n 次方, n!), 找出后, f(n) = 该数量级, 若 T(n)/f(n) 求极限可得到一常数 c, 则时间复杂度 T(n) = O(f(n))
下面是各种常见函数的时间复杂度趋势图:
增长趋势是 O(1) <O(log n) < O(√n) < O(n) < O(nlog n) < O(n^2) < O(2^n) < O(n!)
看过了定义概念和趋势图之后其实还是不太明白时间复杂度是什么, 所以有必要把时间复杂度再说白一点. 挑几个经典的并且常见的时间复杂度来举例说明.
我理解的是计算时间复杂度时要本着几个原则:
去掉 (忽略) 常数项
系数是常数的, 要把这个系数去掉
只留最高次项
比如 T(n) = 4n^3 + 2n^2 + 5n + 10
去掉常数项: T(n) = 4n^3 + 2n^2 + 5n
去掉常数系数: T(n) = n^3 + n^2 + n
只留最高次项: T(n) = n^3
所以最后时间复杂度为 O(n^3)
注: n^3 表示 n 的 3 次幂.
复杂度 O(1) : 常数级
例 1:
- - (void)printHello:(int)n {
- NSLog(@"Hello world!");
- }
方法中只有一句 NSLog 语句, 也就是说程序执行这段代码的总操作单元数量 (总次数) 恒等于常数 1. 代码的执行次数与问题规模 n 无关, 这样的代码段时间复杂度就是 O(1) .
例 2:
- - (void)conditionalStatement:(int)n {
- if (n> 10) {
- NSLog(@"大于 10");
- }
- else {
- NSLog(@"不大于 10");
- }
- }
方法中先要对参数 n 进行判断, 此处要执行一次. 然后如果 n> 10 执行 NSLog(@"大于 10");, 如果 n <= 10 那么执行 NSLog(@"不大于 10");. 所以无论 n 等于几, 代码段执行的总次数恒等于常数 2. 或者说最坏的情况 (执行次数最多的时候) 也是常数 2. 所以它的时间复杂度仍然是 O(1).
复杂度 O(log n): 对数级增长
例 3:
- - (void)exampleForLogN:(int)n {
- int num1 = 0, num2 = 0;
- for(int i=0; i<n; i++){
- num1 += 1;
- for(int j=1; j<=n; j*=2){
- num2 += num1;
- }
- }
- }
语句 int num1 = 0, num2 = 0; 的执行次数 (频度) 为 1;
语句 i=0; 的频度为 1;
语句 i<n; i++; num1+=1; j=1; 的频度为 n;
语句 j<=n; j*=2; num2+=num1; 的频度为 n*log n;
T(n) = 2 + 1 + 4n + 3n*log n, 当 n 趋近无穷大时, 复杂度会越来越趋近最高幂次项 3n*log n 的值, 再去掉系数 3, 就是我们要算的时间复杂度 O(log n).
其中最内层的 num2+=num1; 是执行最多的语句, 它的执行次数为什么是 n*log n 呢?
分析一下: 语句 num2+=num1; 处在两层嵌套的循环之中, 如果外层循环次数为 n , 内层循环次数为 m , 那么语句 num2+=num1; 就会执行 n * m 次. 代码中很容易看出来外层循环就是执行 n 次, 而内层循环到底执行了多少次取决于 j*=2 这句代码的趋势. j 从 1 开始计数, j 的变化趋势是 j=2 --> j=4 --> j=8 --> j=16... 也就是 j 是以指数趋势增长, 假设当 j = n 时执行了 t 次, 那么就有 2^t=n(2 的 t 次幂等于 n), 则有次数 t=log n(log 以 2 为底 n 的对数), 也就是说问题规模为 n 时, 内层循环执行了 log n 次.
复杂度 O(n): 线性增长
例 4:
- - (void)exampleForSum:(int)n {
- int sum = 1;
- for (int i = 0; i <n; i++) {
- sum += i;
- }
- NSLog(@"%d", sum);
- }
语句 int sum = 1; 执行 1 次;
语句 int i = 0; 执行 1 次;
语句 i < n; i++ sum += i; 都会执行 n 次;
语句 NSLog(@"%d", sum); 执行 1 次;
所以 T(n)=3+3n, 当 n 趋近无穷大时, 有复杂度 T(n) = O(n), 即这段代码的时间复杂度是 O(n).
例 5:
- - (NSInteger)findMaxElement:(NSArray *)array {
- NSInteger max = [array.firstObject integerValue];
- for (int i = 0; i < array.count; i++) {
- if ([array[i] integerValue]> max) {
- max = [array[i] integerValue];
- }
- }
- return max;
- }
n 为数组 array 的元素个数, 则最坏情况下需要比较 n 次以得到最大值, 所以算法复杂度为 O(n).
例 6:
- int factorial(int n) {
- if (n == 0) {
- return 1;
- }
- else {
- return n * factorial(n - 1);
- }
- }
阶乘: 给定规模 n, 算法基本步骤执行的数量为 n, 所以算法复杂度为 O(n).
复杂度 O(n^2): 乘方级增长
例 7:
- - (NSInteger)SumMN:(NSInteger)n {
- NSInteger sum = 0;
- for (int x = 0; x <n; x++) {
- for (int y = 0; y < n; y++) {
- sum += x * y;
- }
- }
- return sum;
- }
给定规模 n , 则基本步骤的执行数量为 n*n, 所以算法复杂度为 O(n^2).
例 8:
- - (NSInteger)findInversions:(NSArray *)array {
- NSInteger inversions = 0;
- for (int i = 0; i < array.count; i++) {
- for (int j = i + 1; j < array.count; j++) {
- if (array[i]> array[j]) {
- inversions++;
- }
- }
- }
- return inversions;
- }
单位操作 if 语句在两层 for 循环中, 它的总次数是一个等差数列之和, 即首数加尾数乘以个数除以 2.
当 i=0 时, 内层执行 (n-1) 次, 当 i=n-1 时, 内层执行 0 次, 首数加尾数(n-1+0), 乘以个数除以 2,T(n) = (n-1)*n/2.
n 为数组 array 的大小, 则基本步骤的执行数量约为 n*(n-1)/2, 所以算法复杂度为 O(n2).
复杂度 O(2^n): 指数级增长
例 9:
- - (NSInteger)Calculation:(NSInteger)n {
- NSInteger result = 0;
- for (int i = 0; i <(1 << n); i++) {
- result += i;
- }
- return result;
- }
例子中 i 的循环条件是 i < (1 << n),1 << n 表示二进制的 1 --> 0001 向左移 n 位. 比如 n = 1 时向左移 1 位是 0010 , 十进制就是 2, 循环体执行 2 次. n = 2 时向左移 2 位是 0100, 十进制就是 4 , 循环体执行 4 次. 所以循环次数是 2^n, 复杂度是 O(2^n).
例 10:
- - (NSUInteger)fibonacci:(NSUInteger)n {
- if (n <2) {
- return n;
- }
- else {
- return [self fibonacci:n-1] + [self fibonacci:n-2];
- }
- }
这个是斐波那契数列的递归调用求解方式. 当 n<2 时执行次数是一个常数, 即只执行一步返回 n 即可, 复杂度为 O(1). 当 n>=2 时, n 会被一层一层拆分, 一直拆分为 1 或 0 时才能被确定值. 如图:
通过图片能看出总执行次数在以指数级增长, 所以复杂度是 O(2^n).
小训练
测试 1:
- - (void)smallTest1 {
- int i = 2;
- int j = 4;
- int temp = i;
- i = j;
- j = temp;
- }
以上三条单个语句的频度为 1, 该程序段的执行时间是一个与问题规模 n 无关的常数.
算法的时间复杂度为常数阶, 记作 T(n)=O(1).
如果算法的执行时间不随着问题规模 n 的增加而增长, 即使算法中有上千条语句, 其执行时间也不过是一个较大的常数.
此类算法的时间复杂度是 O(1).
测试 2:
- - (void)smallTest2:(int)n {
- int sum = 1;
- for (int i = 0; i < n; i++) {
- for (int j = 0; j < n; j++) {
- sum++;
- }
- }
- }
单纯的双层循环嵌套, 复杂度 O(n^2).
测试 3:
- - (void)smallTest3:(int)n {
- int y = 1;
- int x = 1;
- for (int i = 1 ; i < n; i++) {
- y++; // 语句 1
- for (int j = 0; j < (2*n); j++) {
- x++; // 语句 2
- }
- }
- }
语句 1 的频度是 n-1;
语句 2 的频度是(n-1)*(2n+1) = 2n^2-n-1;
- T(n) = 2n^2-n-1+(n-1) = 2n^2-2;
- f(n) = n^2;
- lim(T(n)/f(n)) = 2 + 2*(1/n^2) = 2;
- T(n) = O(n^2).
测试 4:
- - (void)smallTest4:(int)n {
- int i = 1; // 语句 1
- while (i <= n) {
- i = i*2; // 语句 2
- }
- }
语句 1 的频度是 1,
设语句 2 的频度是 t, 则: 2^t <= n; t <= log_2^n
考虑最坏情况, 取最大值 t=log_2^n,
- T(n) = 1 + log_2^n
- f(n) = log_2^n
- lim(T(n)/f(n)) = 1/log_2^n + 1 = 1
- T(n) = O(log n)
注: log_2^n 表示 log 以 2 为底 n 的对数.
测试 5:
- - (void)smallTest5:(int)n {
- int x = 0;
- for(int i=0;i<n;i++) {
- for(int j=0;j<i;j++) {
- for(int k=0;k<j;k++) {
- x=x+2;
- }
- }
- }
- }
我没有算出来这个数列的求总和到底是什么公式. 不过可以通过观察, 能知道这个算法是三层循环嵌套, 最内层是 O(1)复杂度的执行语句, 第二层和第三层不是以乘方递减, 所以最多是 O(n^3). 如果哪位大神指导具体的求和公式是什么还希望不吝赐教!
参考资料
算法时间复杂度的计算(整理) http://univasity.iteye.com/blog/1164707
算法复杂度分析 - 匠心十年 - 博客园
来源: http://www.jianshu.com/p/78bbe32bf916