玩转算法面试：（二）面试中的复杂度分析
面试中的时间复杂度分析
到底什么是大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
错误：1. 字符串的长度和数组长度混淆
假设最长的字符串长度为s；数组中有n个字符串
对每个字符串排序：O(slogs)
将数组中的每一个字符串按照字母序排序：O(n*slog(s))
将整个字符串数组按照字典序排序：O(s*nlog(n))
解释：对于排序算法时间复杂度理解：
nlogn 是 比较的次数。对整型数组排序只需要nlogn次比较。因为两个整数之间比较
O(1)。两个字符串比较不一样O(s)。
O(n*slog(s)) + O(s*nlog(n)) = O( n*s*logs + s*n*logn )
= O( n*s*(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 的数据进行选择排序，结果计算机假死？
int main() {
for( int x = 1 ; x <= 9 ; x ++ ){
//10的x次方的幂运算
int n = pow(10, x);
clock_t startTime = clock();
int sum = 0;
for( int i = 0 ; i < n ; i ++ )
sum += i;
clock_t endTime = clock();
cout<<"10^"<<x<<" : "<<double(endTime - startTime)/CLOCKS_PER_SEC<<" s"<<endl;
}
return 0;
}
运行结果
如果要想在1s之内解决问题：
- O(n2)的算法可以处理大约104级别的数据；
- O(n)的算法可以处理大约10^8级别的数据；
- O(nlogn)的算法可以处理大约10^7级别的数据
因为我们刚才的操作很简单，就是简单的加法。所以正常还需要低估一点。
空间复杂度
- 多开一个辅助的数组：O(n)
-
多开一个辅助的二维数组：O(n^2)
-
多开常数空间：O(1):原地数组排序
递归调用是有空间代价的：
在递归调用前的函数压入系统栈中的。
空间复杂度O(1):
不管n有多大，只开辟了ret。索引i。
不会增加空间。
int sum1( int n ){
assert( n >= 0 );
int ret = 0;
for( int i = 0 ; i <= n ; i ++ )
ret += i;
return ret;
}
空间复杂度O(n)
深度是n，系统栈中就要装载n个状态。
递归深度就是递归的空间复杂度
int sum2( int n ){
assert( n >= 0 );
if( n == 0 )
return 0;
return n + sum2(n-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 Complexity
int 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 Complexity
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] );
}
}
30n次基本操作：O(n)
因为第二层循环是固定的不受n影响的。
// O(n) Time Complexity
void printInformation(int n){
for( int i = 1 ; i <= n ; i ++ )
for( int j = 1 ; j <= 30 ; j ++ )
cout<<"Class "<<i<<" - "<<"No. "<<j<<endl;
return;
}
o(logn)
对有序数组找到中间元素来判断元素和中间元素的关系。
如果没有查找到，都可以扔掉一半的元素。
二分查找法
n经过几次除以2等于1.log2n = O(logn)
// O(logn) Time Complexity
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(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;
}
常数差距
2n 与 3n的常数级差别
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!"<<endl;
}
O(sqrt(n))
x从n走一直走到根号n结束
// O(sqrt(n)) Time Complexity
bool 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)的算法可以处理大约104级别的数据；
- 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:"<<endl;
for( int i = 10 ; i <= 26 ; i ++ ){
int n = pow(2,i);
int *arr = MyUtil::generateRandomArray(n, 0, 100000000);
clock_t startTime = clock();
MyAlgorithmTester::findMax(arr, n);
clock_t endTime = clock();
cout<<"data size 2^"<<i<<" = "<<n<<"\t";
cout<<"Time cost: "<<double(endTime - startTime)/CLOCKS_PER_SEC<<endl;
delete[] arr;
}
return 0;
}
运行结果：
运行结果
n增加了两倍。时间也大致增加两倍，所以该算法为O(n)级别的。
测试是不是O(n^2)
int main() {
// 数据规模倍乘测试selectionSort
// O(n^2)
cout<<"Test for selectionSort:"<<endl;
for( int i = 10 ; i <= 15 ; i ++ ){
int n = pow(2,i);
int *arr = MyUtil::generateRandomArray(n, 0, 100000000);
clock_t startTime = clock();
MyAlgorithmTester::selectionSort(arr,n);
clock_t endTime = clock();
cout<<"data size 2^"<<i<<" = "<<n<<"\t";
cout<<"Time cost: "<<double(endTime - startTime)/CLOCKS_PER_SEC<<endl;
delete[] arr;
}
return 0;
}
运行结果：大约4倍
数据量n增加了2倍。时间增加了4倍。
int main() {
// 数据规模倍乘测试binarySearch
// O(logn)
cout<<"Test for binarySearch:"<<endl;
for( int i = 10 ; i <= 28 ; i ++ ){
int n = pow(2,i);
int *arr = MyUtil::generateOrderedArray(n);
clock_t startTime = clock();
MyAlgorithmTester::binarySearch(arr,n,0);
clock_t endTime = clock();
cout<<"data size 2^"<<i<<" = "<<n<<"\t";
cout<<"Time cost: "<<double(endTime - startTime)/CLOCKS_PER_SEC<<endl;
delete[] arr;
}
return 0;
}
复杂度试验
log2N / logN
= (log2 + logN)/logN
= 1 + log2/logN
当数据规模变大两倍。运行效率增加1.几倍。
运行结果：
运行结果，变化小
顺序查找转换为二分查找，大大提高效率
int main() {
// 数据规模倍乘测试mergeSort
// O(nlogn)
cout<<"Test for mergeSort:"<<endl;
for( int i = 10 ; i <= 24 ; i ++ ){
int n = pow(2,i);
int *arr = MyUtil::generateRandomArray(n,0,1<<30);
clock_t startTime = clock();
MyAlgorithmTester::mergeSort(arr,n);
clock_t endTime = clock();
cout<<"data size 2^"<<i<<" = "<<n<<"\t";
cout<<"Time cost: "<<double(endTime - startTime)/CLOCKS_PER_SEC<<endl;
delete[] arr;
}
return 0;
}
运行结果：
大约两倍
递归算法的复杂度分析
不是有递归的函数就一定是O(nlogn)!
归并排序 & 快速排序
递归中进行一次递归调用的复杂度分析：
二分查找的递归实现：
左半边或者右半边。无论选那边都只进行一次
每次减半，递归调用的深度为logn，处理问题的复杂度为O(1)
// binarySearch
int 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)
// sum
int sum( int n ){
assert( n >= 0 );
if( n == 0 )
return 0;
return n + sum(n-1);
}
计算x的n次方的幂运算
我在计算x的n次方时候，如果知道n.2次方
就是x^n/2 * x^n/2
// pow2
double 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)
递归中进行多次递归调用
在进行一次递归调用，深度就是次数。
递归树
20 + 21 + 22 + 23 + … + 2n
= 2n+1 - 1
= O(2^n)
指数级的算法：非常慢。n在20左右。30就。
剪枝操作：动态规划。人工智能：搜索树
// f
int f(int n){
assert( n >= 0 );
if( n == 0 )
return 1;
return f(n-1) + f(n-1);
}
归并排序n=8
当n等于8时，层数为3层。每一层处理的数据规模越来越小
一个分成logn层。每一层相加的总体规模还是n
// mergeSort
void 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
一个算法复杂度相对较高，但是它是为了方便其他的操作。
比较高的会均摊到整体。
动态数组（Vector）
template <typename T>
class 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
均摊
第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<int> vec;
for( int i = 0 ; i < n ; i ++ ){
vec.push_back(i);
}
clock_t endTime = clock();
cout<<n<<" operations: \t";
cout<<double(endTime - startTime)/CLOCKS_PER_SEC<<" s"<<endl;
}
return 0;
}
基本满足2倍关系
删除元素缩小空间。
删除
每次普通删除时间复杂度都为O(1)
只剩下n个。这次resize n 删除这个元素为1
临界点震荡无法均摊
重复这个过程，无法均摊，复杂度为O(n)
当元素个数为数组容量的1/4时，resize.为再添加元素留出余地
template <typename T>
class 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;
}
};
运行结果
均摊复杂度：
- 动态数组
- 动态栈
- 动态队列
