0 
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 (for int i = 0) + n + 1 (for i < n) + n (for i++) * [ 1 (for 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。

我做错了什么？

编辑：现在很明显，这本书只讲述了简单语句的时间复杂度。我想现在我的问题是这样的（就像在标题中一样）：算法的时间复杂度是多少？

4

1 回答 1

2

你的书只计算被SimpleStatements执行的人数。

于 2012-10-12T03:42:00.687 回答