到底什么是大O
- n表示数据规模
- O(f(n)) fn是关于n的一个函数。表示运行算法所需要执行的指令数，和f(n)成正比。
- 和a.b.c.d这些常数项关系不大。主要还是看它是哪个层级的。
算法A：O(n) 所需执行指令数：10000n 算法B：O(n^2) 所需执行指令数：10n^2
- n的规模逐渐增大。算法a.b的指令数变化。
-
当n大于某个临界点，a一定会超过b。这是量级上的差距。
-
复杂度很高的算法可能有前面的优势，在数据量很小的时候有意义。
- 对于所有高级的排序算法，当数据规模小到一定程度，我们都可以使用插入排序法进行优化。10%-15%。细节优化。
-
不同时间复杂度随着数据规模的增大
约定
- 在学术界，严格地讲，O(f(n))表示算法执行的上界
- 归并排序算法的时间复杂度是O(nlogn)的，同时也是O(n^2)
- c.nlogn < a.n^2
- 在业界，我们就使用O来表示算法执行的最低上界
- 我们一般不会说归并排序是O(n^2)的
例子
- 以主导作用的为准：
O( nlogn + n ) = O( nlogn )
O( nlogn + n^2 ) = O( n^2 )
- 上面的公式要求算法处理的n是一样的（O( AlogA + B ) 、O( AlogA + B^2 )）
- 上面这种不能省略
- 对邻接表实现的图进行遍历：
- 时间复杂度：O( V + E ) V是顶点个数，E是边的个数。
- 稠密图，甚至完全图。E是近乎V^2级别。
一个时间复杂度的问题
有一个字符串数组，将数组中的每一个字符串按照字母序排序；之后再将整个字符串数组按照字典序排序。整个操作的时间复杂度？
- 每个字符串n*nlogn + 整个字符串数组：nlogn
- 错误字符串的长度和数组长度混淆
假设最长的字符串长度为s；数组中有n个字符串
对每个字符串排序：O(slogs) 将数组中的每一个字符串按照字母序排序：O(n*slog(s))
-
将整个字符串数组按照字典序排序：O(s*nlog(n))
- 解释：对于排序算法时间复杂度理解：
- nlogn 是 比较的次数。对整型数组排序只需要nlogn次比较。
- 因为两个整数之间比较O(1)。两个字符串比较不一样O(s)。
-
O(nslog(s)) + O(snlog(n)) = O( nslogs + snlogn )= O( ns(logs+logn) )
-
字符串数组进行字典序排序。比较nlogn次，每次比较需要O(s)时间复杂度。
算法复杂度在有些情况是用例相关的
插入排序算法 O(n^2)
- 最差情况：O(n^2)
- 最好情况：O(n)：近乎有序
- 平均情况：O(n^2)
快速排序算法 O(nlogn)
- 最差情况：O(n^2) 不随机。有序
- 最好情况：O(nlogn) 随机化标定点
- 平均情况：O(nlogn)
严谨算法最好最差平均。我们经常关注的是大多数。
极端情况心里有数就行了。数据规模的概念
对 10^5 的数据进行选择排序，结果计算机假死？
#include#include #include using namespace std;int main() { // 数据规模每次增大10倍进行测试 // 有兴趣的同学也可以试验一下数据规模每次增大2倍哦:) for( int x = 1 ; x <= 9 ; x ++ ){ int n = pow(10, x); clock_t startTime = clock(); long long sum = 0; for( int i = 0 ; i < n ; i ++ ) sum += i; clock_t endTime = clock(); cout << "sum = " << sum << endl; cout << "10^" << x << " : " << double(endTime - startTime)/CLOCKS_PER_SEC << " s" << endl << endl; } return 0;} 复制代码
运行结果
sum = 4510^1 : 2e-06 ssum = 495010^2 : 1e-06 ssum = 49950010^3 : 4e-06 ssum = 4999500010^4 : 2.9e-05 ssum = 499995000010^5 : 0.000305 ssum = 49999950000010^6 : 0.003049 ssum = 4999999500000010^7 : 0.029234 ssum = 499999995000000010^8 : 0.308056 ssum = 49999999950000000010^9 : 2.98528 s复制代码
如果要想在1s之内解决问题
- O(n^2)的算法可以处理大约10^4级别的数据；
- O(n)的算法可以处理大约10^8级别的数据；
- O(nlogn)的算法可以处理大约10^7级别的数据
因为我们刚才的操作很简单，就是简单的加法。所以正常还需要低估一点,再除以10
空间复杂度
- 多开一个辅助的数组：O(n)
- 多开一个辅助的二维数组：O(n^2)
- 多开常数空间：O(1):原地数组排序
- 递归调用是有空间代价的：
- 在递归调用前的函数压入系统栈中的。
常见的复杂度分析
O(1)
没有数据规模的变化// O(1)void swapTwoInts( int &a , int &b ){ int temp = a; a = b; b = temp; return;}复制代码 O(n)
循环操作次数为c.n。c是个常数不一定为大于1的数// O(n) Time Complexityint sum( int n ){ int ret = 0; for( int i = 0 ; i <= n ; i ++ ) ret += i; return ret;}复制代码 O(n)
循环次数为1/2 * n次
字符串翻转。abc-cba.第一个和倒数第一个。第2个和倒数第二个 扫描一半就交换完了：1/2*n次swap操作：O(n)
void reverse( string &s ){ int n = s.size(); for( int i = 0 ; i < n/2 ; i ++ ) swap( s[i] , s[n-1-i] ); return;}复制代码 O(n^2)
选择排序法。O(n^2) 双重循环: 第一重到n。第二重到n。都是+1. 所执行的指令数和n^2成比例。i = 0;j执行了n-1次 等差数列求和
(n-1) + (n-2) + (n-3) + … + 0= (0+n-1)*n/2= (1/2)n*(n-1)= 1/2*n^2 - 1/2*n= O(n^2) // O(n^2) Time Complexityvoid selectionSort(int arr[], int n){ for(int i = 0 ; i < n ; i ++){ int minIndex = i; for( int j = i + 1 ; j < n ; j ++ ) if( arr[j] < arr[minIndex] ) minIndex = j; swap( arr[i] , arr[minIndex] ); }}复制代码 30n次基本操作：O(n)
因为第二层循环是固定的不受n影响的。// O(n) Time Complexityvoid printInformation(int n){ for( int i = 1 ; i <= n ; i ++ ) for( int j = 1 ; j <= 30 ; j ++ ) cout<<"Class "<<<" - "<<"No. "< < o(logn)
对有序数组找到中间元素来判断元素和中间元素的关系。 如果没有查找到，都可以扔掉一半的元素。二分查找法
// O(logn) Time Complexityint binarySearch(int arr[], int n, int target){ int l = 0, r = n-1; while( l <= r ){ int mid = l + (r-l)/2; if( arr[mid] == target ) return mid; if( arr[mid] > target ) r = mid - 1; else l = mid + 1; } return -1;}复制代码 O(logn)
n经过几次“除以10”操作后，等于0？
log10n = O(logn) while循环中每次除以10，直到0结束。 reverse(s)复杂度：1/2 n次的交换操作。s字符串有多少位，与n一致。
string intToString( int num ){ string s = ""; string sign = "+"; if( num < 0 ){ num = -num; sign = "-"; } while( num ){ s += '0' + num%10; num /= 10; } if( s == "" ) s = "0"; reverse(s); if( sign == "-" ) return sign + s; else return s;}复制代码 O(nlogn)
第二重循环就是n
第一重size+=size就是乘以2.log2n// O(nlogn)void hello(int n){ for( int sz = 1 ; sz < n ; sz += sz ) for( int i = 1 ; i < n ; i ++ ) cout<<"Hello, Algorithm!"< O(sqrt(n))
x从n走一直走到根号n结束// O(sqrt(n)) Time Complexitybool isPrime( int num ){ for( int x = 2 ; x*x <= num ; x ++ ) if( num%x == 0 ) return false; return true;}bool isPrime2( int num ){ if( num <= 1 ) return false; if( num == 2 ) return true; if( num%2 == 0 ) return false; for( int x = 3 ; x*x <= num ; x += 2 ) if( num%x == 0 ) return false; return true;}复制代码 复杂度实验。
我们自以为写出了一个O(nlogn)的算法，但实际是O(n^2)的算法？
如果要想在1s之内解决问题：
- O(n2)的算法可以处理大约10^4级别的数据；
- O(n)的算法可以处理大约10^8级别的数据；
- O(nlogn)的算法可以处理大约10^7级别的数据
前面的常数差距有可能很大。
实验，观察趋势：
每次将数据规模提高两倍，看时间的变化
四个不同复杂度的算法。
namespace MyAlgorithmTester{ // O(logN) int binarySearch(int arr[], int n, int target){ int l = 0, r = n-1; while( l <= r ){ int mid = l + (r-l)/2; if( arr[mid] == target ) return mid; if( arr[mid] > target ) r = mid - 1; else l = mid + 1; } return -1; } // O(N) int findMax( int arr[], int n ){ assert( n > 0 ); int res = arr[0]; for( int i = 1 ; i < n ; i ++ ) if( arr[i] > res ) res = arr[i]; return res; } // O(NlogN) 自底向上 void __merge(int arr[], int l, int mid, int r, int aux[]){ for(int i = l ; i <= r ; i ++) aux[i] = arr[i]; int i = l, j = mid+1; for( int k = l ; k <= r; k ++ ){ if( i > mid ) { arr[k] = aux[j]; j ++;} else if( j > r ){ arr[k] = aux[i]; i ++;} else if( aux[i] < aux[j] ){ arr[k] = aux[i]; i ++;} else { arr[k] = aux[j]; j ++;} } } void mergeSort( int arr[], int n ){ int *aux = new int[n]; for( int i = 0 ; i < n ; i ++ ) aux[i] = arr[i]; for( int sz = 1; sz < n ; sz += sz ) for( int i = 0 ; i < n ; i += sz+sz ) __merge(arr, i, i+sz-1, min(i+sz+sz-1,n-1), aux ); delete[] aux; return; } // O(N^2) 选择排序 void selectionSort( int arr[], int n ){ for(int i = 0 ; i < n ; i ++){ int minIndex = i; for( int j = i + 1 ; j < n ; j ++ ) if( arr[j] < arr[minIndex] ) minIndex = j; swap( arr[i] , arr[minIndex] ); } return; }}复制代码 生成测试用例的代码：
namespace MyUtil { int *generateRandomArray(int n, int rangeL, int rangeR) { assert( n > 0 && rangeL <= rangeR ); int *arr = new int[n]; srand(time(NULL)); for (int i = 0; i < n; i++) arr[i] = rand() % (rangeR - rangeL + 1) + rangeL; return arr; } int *generateOrderedArray(int n) { assert( n > 0 ); int *arr = new int[n]; for (int i = 0; i < n; i++) arr[i] = i; return arr; }}复制代码 测试是不是O(n)级别的
int main() { // 数据规模倍乘测试findMax // O(n) cout<<"Test for findMax:"< 运行结果：
Test for findMax:data size 2^10 = 1024 Time cost: 5e-06 sdata size 2^11 = 2048 Time cost: 7e-06 sdata size 2^12 = 4096 Time cost: 1.2e-05 sdata size 2^13 = 8192 Time cost: 2.5e-05 sdata size 2^14 = 16384 Time cost: 4.7e-05 sdata size 2^15 = 32768 Time cost: 9.2e-05 sdata size 2^16 = 65536 Time cost: 0.000169 sdata size 2^17 = 131072 Time cost: 0.000431 sdata size 2^18 = 262144 Time cost: 0.000737 sdata size 2^19 = 524288 Time cost: 0.001325 sdata size 2^20 = 1048576 Time cost: 0.002489 sdata size 2^21 = 2097152 Time cost: 0.005739 sdata size 2^22 = 4194304 Time cost: 0.011373 sdata size 2^23 = 8388608 Time cost: 0.019566 sdata size 2^24 = 16777216 Time cost: 0.040289 sdata size 2^25 = 33554432 Time cost: 0.095169 sdata size 2^26 = 67108864 Time cost: 0.201682 sdata size 2^27 = 134217728 Time cost: 0.330673 sdata size 2^28 = 268435456 Time cost: 0.750136 s复制代码
n增加了两倍。时间也大致增加两倍，所以该算法为O(n)级别的。
测试是不是O(n^2)
int main() { // 数据规模倍乘测试selectionSort // O(n^2) cout<<"Test for selectionSort:"< 运行结果：大约4倍
Test for Selection Sort:data size 2^10 = 1024 Time cost: 0.001581 sdata size 2^11 = 2048 Time cost: 0.006221 sdata size 2^12 = 4096 Time cost: 0.021913 sdata size 2^13 = 8192 Time cost: 0.081103 sdata size 2^14 = 16384 Time cost: 0.323263 sdata size 2^15 = 32768 Time cost: 1.32474 sdata size 2^16 = 65536 Time cost: 5.19642 s复制代码
数据量n增加了2倍。时间增加了4倍。
测试是不是O(logN)
int main() { // 数据规模倍乘测试binarySearch // O(logn) cout<<"Test for binarySearch:"< 复杂度试验
log2N / logN= (log2 + logN)/logN= 1 + log2/logN复制代码
当数据规模变大两倍。运行效率增加1.几倍。
运行结果：
Test for Binary Search:data size 2^10 = 1024 Time cost: 1e-06 sdata size 2^11 = 2048 Time cost: 0 sdata size 2^12 = 4096 Time cost: 0 sdata size 2^13 = 8192 Time cost: 2e-06 sdata size 2^14 = 16384 Time cost: 1e-06 sdata size 2^15 = 32768 Time cost: 1e-06 sdata size 2^16 = 65536 Time cost: 1e-06 sdata size 2^17 = 131072 Time cost: 2e-06 sdata size 2^18 = 262144 Time cost: 3e-06 sdata size 2^19 = 524288 Time cost: 1e-06 sdata size 2^20 = 1048576 Time cost: 4e-06 sdata size 2^21 = 2097152 Time cost: 3e-06 sdata size 2^22 = 4194304 Time cost: 3e-06 sdata size 2^23 = 8388608 Time cost: 4e-06 sdata size 2^24 = 16777216 Time cost: 4e-06 sdata size 2^25 = 33554432 Time cost: 1.2e-05 sdata size 2^26 = 67108864 Time cost: 9e-06 sdata size 2^27 = 134217728 Time cost: 1.1e-05 sdata size 2^28 = 268435456 Time cost: 2.4e-05 s复制代码
运行结果，变化小
顺序查找转换为二分查找，大大提高效率
测试是不是O(NlogN)
和O(N)差不多
int main() { // 数据规模倍乘测试mergeSort // O(nlogn) cout<<"Test for mergeSort:"< 运行结果：
Test for Merge Sort:data size 2^10 = 1024 Time cost: 0.000143 sdata size 2^11 = 2048 Time cost: 0.000325 sdata size 2^12 = 4096 Time cost: 0.000977 sdata size 2^13 = 8192 Time cost: 0.001918 sdata size 2^14 = 16384 Time cost: 0.003678 sdata size 2^15 = 32768 Time cost: 0.007635 sdata size 2^16 = 65536 Time cost: 0.015768 sdata size 2^17 = 131072 Time cost: 0.034462 sdata size 2^18 = 262144 Time cost: 0.069586 sdata size 2^19 = 524288 Time cost: 0.136214 sdata size 2^20 = 1048576 Time cost: 0.294626 sdata size 2^21 = 2097152 Time cost: 0.619943 sdata size 2^22 = 4194304 Time cost: 1.37317 sdata size 2^23 = 8388608 Time cost: 2.73054 sdata size 2^24 = 16777216 Time cost: 5.60827 s复制代码
大约两倍
递归算法的复杂度分析
- 不是有递归的函数就一定是O(nlogn)!
二分查找的递归实现：
左半边或者右半边。无论选那边都只进行一次
每次减半，递归调用的深度为logn，处理问题的复杂度为O(1)
// binarySearchint binarySearch(int arr[], int l, int r, int target){ if( l > r ) return -1; int mid = l + (r-l)/2; if( arr[mid] == target ) return mid; else if( arr[mid] > target ) return binarySearch(arr, l, mid-1, target); else return binarySearch(arr, mid+1, r, target);}复制代码 如果递归函数中，只进行一次递归调用，
递归深度为depth; 在每个递归函数中，时间复杂度为T; 则总体的时间复杂度为O( T * depth )
求和递归实现
递归深度：n
时间复杂度：O(n)
// sumint sum( int n ){ assert( n >= 0 ); if( n == 0 ) return 0; return n + sum(n-1);}复制代码 计算x的n次方的幂运算
// pow2double pow( double x, int n ){ assert( n >= 0 ); if( n == 0 ) return 1.0; double t = pow(x, n/2); //奇数 if( n%2 ) return x*t*t; return t*t;}复制代码 递归深度：logn
时间复杂度：O(logn)递归中进行多次递归调用
递归树的深度是N
2^0 + 2^1 + 2^2 + 2^3 + … + 2^n
= 2n+1 - 1 = O(2^n)
指数级的算法：非常慢。n在20左右。30就非常慢 剪枝操作：动态规划。人工智能：搜索树
// fint f(int n){ assert( n >= 0 ); if( n == 0 ) return 1; return f(n-1) + f(n-1);}复制代码 归并排序n=8
树的深度是logN 当n等于8时，层数为3层。每一层处理的数据规模越来越小
一个分成logn层。每一层相加的总体规模还是n
// mergeSortvoid mergeSort(int arr[], int l, int r){ if( l >= r ) return; int mid = (l+r)/2; mergeSort(arr, l, mid); mergeSort(arr, mid+1, r); merge(arr, l, mid, r);}复制代码 均摊复杂度分析 Amortized Time analysis
一个算法复杂度相对较高，但是它是为了方便其他的操作。
比较高的会均摊到整体。
动态数组（Vector）
templateclass MyVector{private: T* data; int size; // 存储数组中的元素个数 int capacity; // 存储数组中可以容纳的最大的元素个数 // O(n)：一重循环。 void resize(int newCapacity){ assert( newCapacity >= size ); T *newData = new T[newCapacity]; for( int i = 0 ; i < size ; i ++ ) newData[i] = data[i]; delete[] data; data = newData; capacity = newCapacity; }public: MyVector(){ data = new T[100]; size = 0; capacity = 100; } ~MyVector(){ delete[] data; } // Average: O(1) void push_back(T e){ //动态数组 if( size == capacity ) resize( 2* capacity ); data[size++] = e; } // O(1) T pop_back(){ assert( size > 0 ); size --; //size是从0开始的。也就是0号索引size为1. //所以要拿到最后一个元素，就得size-1 return data[size]; }};复制代码
均摊
第n+1次会花费O(n)但是会把这n分摊到前面n次操作。也就是变成了O(2)
还是常数O(1)级的。 resize是有条件的，而不是每次都调用。int main() { for( int i = 10 ; i <= 26 ; i ++ ){ int n = pow(2,i); clock_t startTime = clock(); MyVector vec; for( int i = 0 ; i < n ; i ++ ){ vec.push_back(i); } clock_t endTime = clock(); cout< <<" operations: \t"; cout< 1024 operations: 2.5e-05 s2048 operations: 2.9e-05 s4096 operations: 7.4e-05 s8192 operations: 0.000154 s16384 operations: 0.000265 s32768 operations: 0.000391 s65536 operations: 0.001008 s131072 operations: 0.002006 s262144 operations: 0.003863 s524288 operations: 0.005842 s1048576 operations: 0.014672 s2097152 operations: 0.029367 s4194304 operations: 0.06675 s8388608 operations: 0.124446 s16777216 operations: 0.240025 s33554432 operations: 0.486061 s67108864 operations: 0.960224 s复制代码
基本满足2倍关系
删除元素缩小空间。
每次普通删除时间复杂度都为O(1)
只剩下n个。这次resize n 删除这个元素为1
重复这个过程，无法均摊，复杂度为O(n)
当元素个数为数组容量的1/4时，resize.为再添加元素留出余地
templateclass MyVector{private: T* data; int size; // 存储数组中的元素个数 int capacity; // 存储数组中可以容纳的最大的元素个数 // O(n) void resize(int newCapacity){ assert( newCapacity >= size ); T *newData = new T[newCapacity]; for( int i = 0 ; i < size ; i ++ ) newData[i] = data[i]; delete[] data; data = newData; capacity = newCapacity; }public: MyVector(){ data = new T[100]; size = 0; capacity = 100; } ~MyVector(){ delete[] data; } // Average: O(1) void push_back(T e){ if( size == capacity ) resize( 2* capacity ); data[size++] = e; } // Average: O(1) T pop_back(){ assert( size > 0 ); T ret = data[size-1]; size --; if( size == capacity/4 ) resize( capacity/2 ); //resize之后会把data[size]元素抹掉 return ret; }};复制代码
运行结果
2048 operations: 4.3e-05 s4096 operations: 6.3e-05 s8192 operations: 0.000107 s16384 operations: 0.000316 s32768 operations: 0.000573 s65536 operations: 0.001344 s131072 operations: 0.001995 s262144 operations: 0.004102 s524288 operations: 0.008599 s1048576 operations: 0.014714 s2097152 operations: 0.027181 s4194304 operations: 0.063136 s8388608 operations: 0.126046 s16777216 operations: 0.242574 s33554432 operations: 0.456381 s67108864 operations: 0.96618 s134217728 operations: 1.76422 s复制代码
均摊复杂度
- 动态数组
- 动态栈
- 动态队列
-------------------------华丽的分割线--------------------
看完的朋友可以点个喜欢/关注，您的支持是对我最大的鼓励。
个人博客和
想了解更多，欢迎关注我的微信公众号：番茄技术小栈