时间复杂度概念

Question

如题所述

Answer 1

用时间复杂度、空间复杂度校验一个程序写的好坏。

给定两个函数 f(n) 和 g(n)，如果存在一个整数 N ，使得对于所有的 n>N ，f(n)总是比g(n)大，那么，我们说 f(n)的增长渐近快于g(n)。

比如：当 n 的值变得非常大的时候，3n+1 已经没法和 2n ² 的结果相比较，最终结果几乎可以忽略不计。

于是我们得出这样一个结论：判断一个算法的效率时，函数中的常数项和其他次项长可以忽略，更应该关注主项(最高项)的阶数。

常数阶 O(1) 、线性阶 O(n)、平方阶 O(n ² )、对数阶 O(logn)、nlogn阶 O(nlogn)、立方阶 O(n ³ )、指数阶 O(2 ² )

O(1) < O(logn) < O(n) < O(nlogn) < O(n ² ) < O(n ³ ) < O(2 ⁿ ) < O(n!) < O(n ⁿ )

必记的四个：插入排序、堆排序、归并排序、快速排序