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
            }
        }
    }
}

这在大 theta 中的运行时间是多少？

我最好的猜测，瞎猜:我总是看到嵌套的 for 循环是 O(n^k)，其中 k 是循环的数量，所以循环是 O(n^4)，那么我会乘以 O(1) 常数时间？在 big theta 中这一切会是什么？

Answer 1

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

但是，如果将 5 更改为 n，则它将是 theta(n^4)，因为您将执行恰好 n^4 个常数时间操作。