例如：
void fun(int n)
{
    int i=0,j;
    do
    {
        for (j=0;j<n;j++)
            i+=j;    
    }while (i<n+1);
}

讲下详细的解题过程

O(n）

[[it] 本帖最后由 jdh99 于 2008-11-14 10:50 编辑 [/it]]

如何计算一个算法的时间复杂度

题目就不明白什么意思
void fun(int n)
{
    int i=0,j;
    do
    {
        for (j=0;j<n;j++)
            i+=j;   
    }while (i<n+1);
}

for(i=0;i<n+1;)
    for (j=0;j<n;i+=j,j++);

这意思

[[it] 本帖最后由 scheelite 于 2008-11-14 11:04 编辑 [/it]]

外循环无用，复杂度T(n)

一般是计算  最内层循环的 那个对程序总运行时间贡献最大的 操作 的 执行次数

CPU的处理能力一般是每秒执行百万条指令   两者对照一下就可以粗略估计程序的运行时间

你可以试试估计一下汉诺塔（64层）程序的运算时间 2^64-1
2^10≈10^3  2^64≈16*10^18=16*10^12*10^6=310*16世纪
//执行10^6次条指令需1秒  10^8秒≈3.1年  10^10秒 ≈ 3.1世纪

[[it] 本帖最后由 网易 于 2008-11-14 12:55 编辑 [/it]]

我承认我是菜鸟，算复杂度只想到求循环次数，而且是能看懂程序的前提下

书上讲得很清楚也很详细。大O的定义和在数学分析中的定义是一样的。

O(n)

void fun(int n)
{
    int i=0,j;
    do
    {
        for (j=0;j<n;j++)
            i+=j;   
    }while (i<n+1);
}
大哥，这程序好像太那个了
设n=4
循环
1 j=0
2 j<4
3 i=0+0
4 j=1
5 j<4
6 i=0+1
7 j=2
8 j<4
9 i=1+2
10 j=3
11 j<4
12 i=3+3
13 j!<4
退出for循环
i=6!<(n+1)=4
do循环只做了一次
这是啥意思

还没见过用T（n）表示复杂度的  T（n）表示时间的吧

O（g(n)） ⊙(g(n))  Ω(g(n))　　都见过了  不过很少见人用