有木有人跟我一样，看到复杂度三个字，能熟练说出常见算法的时间复杂度，但潜台词：“诶？怎么算来着？怎么算来着？”。
为了以后不再一脸懵逼二脸懵逼对角线懵逼，小豆就写了这篇小笔记。
参考链接：https://blog.csdn.net/daijin888888/article/details/66970902
简介
百度百科如下定义时间复杂度：
一般情况下，算法中基本操作重复执行的次数是问题规模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) 越小，算法的时间复杂度越低，算法的效率越高。
计算方法
用大写O()来体现算法时间复杂度的记法，我们称之为大O记法，推导方法如下：
- 用常数1取代运行时间中的所有加法常数；
- 在修改后的运行次数函数中，只保留最高阶项；
- 如果最高阶项存在且不是1，则去除与这个项目相乘的常数，得到的结果就是大O阶。
常数阶：O(1)；
线性阶：O(n);
对数阶：O(logn)；
平方阶：O(n^2)；
O(1) 常数阶 < O(logn) 对数阶 < O(n) 线性阶 < O(nlogn) < O(n^2) 平方阶 < O(n^3) < O(2^n) < O(n!) < O(n^n)
示例
- 举个对数阶的🌰
int count = 1;
while (count < n)
{
count = count * 2;
}
有多少个2相乘后大于n，则会退出循环，设循环次数为x，n = 2^x，得到x = logn，所以这个算法的时间复杂度为O(logn)。
- 再举个平方阶的🌰
for (NSUInteger i = 0; i < array.count; i++)
{
for (NSUInteger j = 0; j < array.count-1-i; j++)
{
if ([array[j] floatValue] > [array[j+1] floatValue])
{
[array exchangeObjectAtIndex:j withObjectAtIndex:j+1];
}
}
}
- 最后一个🌰
//执行1次
int i, sum = 0, n = 100;
// 执行 n+1 次
for( i = 1; i <= n; i++)
{
//执行n次
sum = sum + i;
}
根据注释可得到，该算法执行的总次数为：1+(n+1)+n=2n+2，根据大O记法推导：
第一步用常数1取代运行时间中的所有加法常数，得到2n+1;
第二步保留最高阶项，得到2n;
第三步如果最高阶项存在且不是1，则去除与这个项目相乘的常数，得到该算法的时间复杂度为O(n)。
