Question

时间复杂度 T(n)=O(f(n)),的 O什么意思

时间复杂度 T(n)=O(f(n)),的 O什么意思数据结构里的

Answer 1

O(n)这个大O表示的是最坏情况下的时间复杂度，就比如你举的例子，一共n^3次乘法和n^3次加法，那么加起来就是2×n^3。然后如果有一个表达式f(n)，使得n趋于无穷大的时候，lim(2×n^3)/f(n)=常数c，那么就可以用大O表示。表示为O(f(n))，而且规定f(n)的表达式是不带常数的系数的，那么在这里f(n)=n^3。一般用大O表示算法复杂度只需要取次数最高的项，而且去掉系数就OK了，不用每次都这么算的。三重循环而且每重循环都执行n次的话直接O(n^3)就好了。