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)