2.1算法的时间复杂度与空间复杂度

本篇博客介绍算法的时间复杂度与空间复杂度

一、算法效率

算法好坏从时间和空间两个维度衡量

二、时间复杂度

1．概念

时间复杂度是算法中基本操作的执行次数，定量描述了算法的运行时间

2．注意

（1）时间复杂度是偏保守的估计量，可理解为最低的预期
（2）时间复杂度是一个数量级，表征大概执行次数，采用大O渐进表示法

• 如果是常数次计算，时间复杂度为O(1)
• 在运行次数函数中，只保留次数最高的那一项
• 要省略最高阶项前面的常数
  
  （3）时间复杂度实际上是一个函数f(x)，注意与平时编程时调用的函数进行区分，是算法精确的执行次数

3．例子

（1）冒泡排序的时间复杂度

void BubbleSort(int* a, int n) 
{ assert(a); for (size_t end = n; end > 0; --end) { int exchange = 0; for (size_t i = 1; i < end; ++i) { if (a[i-1] > a[i]) { Swap(&a[i-1], &a[i]); exchange = 1; } } if (exchange == 0) break; } 
} 

（2）二分查找的时间复杂度

int BinarySearch(int* a, int n, int x) 
{ assert(a); int begin = 0; int end = n-1; while (begin <= end) { int mid = begin + ((end-begin)>>1); if (a[mid] < x) begin = mid+1; else if (a[mid] > x) end = mid-1; else return mid; } return -1; 
}

注意：只有以2为底的对数才可以简写成logN

（3）递归函数的时间复杂度

long long Fac(size_t N) 
{ if(0 == N) return 1; return Fac(N-1)*N; 
} 

三、空间复杂度

1．概念

空间复杂度是算法运行过程中临时占用存储空间大小的量度，算的是变量的个数，研究额外申请的空间

2．例子

long long Fac(size_t N) 
{ if(N == 0) return 1; return Fac(N-1)*N; 
}

解析：从Fac(N)到Fac(0)共调用Fac()函数N+1次，数量级是N，因此空间复杂度为O(N)