用这篇博客记录一下学习如何计算时间复杂度的过程。本文会从时间复杂度的定义到具体案例的练习，让初学者对时间复杂度有个基本印象。
摘自《维基百科》
在计算机科学中，算法的时间复杂度是一个函数，它定性描述该算法的运行时间。这是一个代表算法输入值的字符串的长度的函数。时间复杂度常用大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(n*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 次，所以内外层相乘即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)。如果哪位大神指导具体的求和公式是什么还希望不吝赐教😁！
