数据结构时间复杂度怎么算

Question

如题所述

Answer 1

就是看它运行多少次啊。。。。
这个运行次数是：1 + 2*3/2 + 3*4 / 2 + 。。。 + n * (n + 1) / 2
即an = n * (n + 1) / 2的数列前n项之和
具体的求和我已经还给数学老师了。。。但是显然n项（n^2）级别的数相加，结果为n^3级别
// 刚刚请教了同学，具体数值是 n * (n + 1) * (n + 2) / 6
即这个算法的时间复杂度是O(n^3),大O符号是去掉了系数和低次幂之后的级别。
比如一个程序运行的次数是 n^3 / 100 + 100 * n^2 + n + 10 那么它的时间复杂度是O(n^3)
一般来说，我们可以通过嵌套循环的层数，来初步估计时间复杂度

Answer 2

n^3 计算每个for循环的可能的最大值，相乘

Answer 3

追答

第三题答案

就是算最深层的循环语句运行的次数

追问

我知道答案，想问怎么算出来的

追答

本回答被网友采纳

Answer 4

Answer 5

简单理解，时间复杂度就是执行语句被调用了多少次。
(1)如果只调用了一次，如：
x=5;
if(x<-4)
{x=x+4;}
else
{x=x+3;}
在大括号中的内容，只会调用一个语句，那么O(n)=1;
(2)如果调用了两次，如：
x=5;
if(x<-4)
{x=x+4;}
else
{x=x+3;}
x=x+56;
在大括号中的内容，只会调用一个语句，但是在最后，还有一个计算公式要调用语句；总共加起来就是调用2次。那么O(n)=2;
（3）用1个FOR循环调用
for(x=0;x<n;x++)
{x=x+1;}
x会从0到n-1循环，执行的语句就是将当前x值加入新的x中，总共调用n次；那么O(n)=n;
(4）用2个嵌套FOR循环调用
for(x=0;x<n;x++)
{
for(y=1;y<=n;y++)
{x=x+y;}
}
遇到嵌套循环，可以先将外面的FOR语句中的变量固定为初始值x=0，主要看里面的FOR语句的时间复杂度，很明显，里面语句执行次数是从1到n总共调用n次，O(n)=n；这还只是x=0时的调用。x可以从0到n-1，共n次。每次调用都会执行n次调用y的情况，因此，执行语句x=x+y；总共会调用n*n次。O(n)=n^2。

数执行语句的执行次数，就是时间复杂度。注意：
(1)找到正确的执行语句。
(2)for循环中的初始值和终止值。
for(i=0;i<n;i++) i值变化是从0到n-1，共n次。
for(i=0;i<=n;i++) i值变化是从0到n，共n+1次。
(3)注意for循环的调用顺序，从里面到外面进行的。