perl - Perl foreach 在哈希键上的复杂性

Question

这段代码的复杂度是多少？

foreach $var (keys %varset) { 
  print "${var}\n";
}

是O(n^2)还是O(n)，也就是说，每次迭代都会调用keys操作还是只调用一次？

Answer 1

是 O(n)。当foreach循环开始时，表达式在列表上下文中进行计算，然后循环遍历该列表。一方面，不能保证后续调用keys会以相同的顺序返回键，甚至返回相同的键，那么如果它重新评估表达式，它如何确定下一个元素呢？

Answer 2

您没有指定哪种资源，以及您是否对最佳、平均或最坏情况感兴趣，所以我将全部提供。

---

的 CPU 使用率for (keys %hash)，无论是最好的还是最坏的情况，都是： Θ(N) 获取键 + Θ(N) 迭代它们 = Θ(N)

的内存使用for (keys %hash)，无论是最好的还是最坏的情况，都是： Θ(N) 来获取键 + Θ(1) 来迭代它们 = Θ(N)

一些 foreach 循环被优化为不使用内存。

的内存使用量for (NON_CONST_EXPR..NON_CONST_EXPR)，无论是最好还是最坏的情况，都是：Θ(1)
的内存使用量for (@a)，无论是最好的还是最坏的情况，都是：Θ(1)

---

Θ(f()) 比 O(f()) 更具体。如果某事物是 Θ(f())，那么它既是 O(f()) 又是 Ω(f())。