数据结构中 时间复杂度是如何计算的（详细点啊……）

来源：百度知道 编辑：UC知道 时间：2024/07/04 14:37:50
我是一个超级菜鸟。在算数据结构的时间复杂度时，不知道如何下手，请高手详细指点一下~越详细越好！如果答的很好，可以追加分数的！
O(1)<O(logn)<O(n)<O(nlogn) <O(n2)<O(n3)
我想问一下的是对不同的程序（像do-while和for等）怎么判断它应该是O（1）还是O（n）或别的？

时间复杂度：基本操作重复执行的次数的阶数 T(n)=o(f(n))
以下六种计算算法时间的多项式是最常用的。其关系为：
O(1)<O(logn)<O(n)<O(nlogn) <O(n2)<O(n3)
指数时间的关系为：
O(2n)<O(n!)<O(nn)
当n取得很大时，指数时间算法和多项式时间算法在所需时间上非常悬殊。
例1：NXN矩阵相乘
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{c[i][j]=0;
for(k=1;k<=n;k++)
c[i][j]=c[i][j]+a[i][k]*b[k][j];
}

T(n)=n^3