for (int i = 0; i < n; i++ ) {
    for (int j = 0; j < n; j++ {
        Simple Statement
    }
}
for (int k = 0; i < n; k++ {
    Simple Statement
    Simple Statement
    Simple Statement
    Simple Statement
    Simple Statement
}
    Simple Statement*25

对于嵌套循环,我发现时间复杂度为1(对于int i=0)+n+ 1(对于i<n)+n(对于i++)*[1(对于int j=0)+1 +n(对于j<n)+n(对于j++)] +n(对于简单语句)。这是(1+n+1+n)(1+1+n+n)+n=(2+2n)(2+2n)+n=4n^2+9n+4。
对于下面的循环,我发现时间复杂度为1(对于int k=0)+n+ 1(对于i<n)+n(对于k++)+5n(对于五个简单语句)。这是1+n+1+n+5n=7n+2对于接下来的25个简单语句,我发现它们的时间复杂度为25。
总时间复杂度为4n^ 2+8n+4+5n+ 2+25=4n^ 2+16n+31,但我的书说时间复杂度为n^ 2+5n+25。
我做错了什么?
编辑:很明显,这本书只讲述了简单陈述的时间复杂性。我想现在我的问题是(正如标题中所说的):算法的时间复杂度是多少?

最佳答案

你的书只计算执行的SimpleStatements个数。

关于algorithm - 以下算法的时间复杂度是多少?,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/12851857/

10-10 18:55