algorithm - 具有哈希表查找的四嵌套循环的大 theta

Question

for (int i = 0; i < 5; i++) {
    for (int j = 0; j < 5; j++) {
        for (int k = 0; k < 5; k++) {
            for (int l = 0; l < 5; l++) {
                look up in a perfect constant time hash table
            }
        }
    }
}

大θ的运行时间是多少？

我最好的猜测，在黑暗中拍摄：我总是看到嵌套的for循环是O（n ^ k），其中k是循环数，所以循环是O（n ^ 4），然后我会乘以O (1) 恒定时间？这一切会是什么？

Answer 1

如果您认为访问哈希表实际上是 theta(1)，那么该算法也在 theta(1) 中运行，因为它仅在哈希表上进行常数 (5^4) 查找。

但是，如果您将 5 更改为 n，它将是 theta(n^4)，因为您将执行 n^4 个恒定时间操作。

Answer 2

big-theta 运行时间为Θ(n^4).

Big-O 是一个上界，而 big-theta 是一个紧界。这意味着说代码O(n^5)也是正确的（但Θ(n^5)不是），big-O 中的任何内容都必须渐近大于或等于n^4.

我假设5可以替换为另一个值（即 is n），如果不是，则循环将在恒定时间（O(1)and Θ(1)）中运行，因为5^4它是恒定的。

Answer 3

使用 Sigma 符号：

实际上，最内层循环内的指令将执行625次。