时间复杂度的定义
时间复杂度的定义是度量算法执行时间随输入规模增长而增长的量度,通常用大 O 记号表示它反映了算法在解决问题时所耗费的时间资源,也可以理解为算法的运行效率。时间复杂度分析的目的是确定算法执行时间与输入规模之间的关系,并帮助我们选择更高效的算法来解决问题。
时间复杂度的常用复杂度
- **O(1)**:常数时间复杂度,表示算法的运行时间不随输入规模的增加而增加。
- **O(log n)**:对数时间复杂度,表示算法的运行时间以对数方式增长,如二分查找。
- **O(n)**:线性时间复杂度,表示算法的运行时间随输入规模线性增长。
- **O(n log n)**:表示算法的运行时间在 n 和 nlogn 之间增长,如快速排序。
- **O(n^2)**:平方时间复杂度,表示算法的运行时间是输入规模的平方。
归并排序的时间复杂度
有这样一种情况
T(n)=aT(n/b)+O+f(n)
在这个表达式中
a指子问题的个数
b每个子问题占原文的几分之几
f(n)对于递归来讲吗,就是拆开跟合并n个规模的问题所需要的时间。
对于这个式子,有以下几种情况
case1
log \sideset{}{_a}b < d
那么时间复杂度为:
O(N^{d})
case2
log \sideset{}{_a}b > d
那么时间复杂度为:
O(log_{b}a)
case 3
log \sideset{}{_a}b = d
那么时间复杂度为:
O(N^{d}\times log_2N)