algorithm - 确定多个函数调用的运行时间

Question

假设我有一个函数 f(K)，它以 K 的分摊对数时间运行，但最坏情况时间为线性。运行时间是多少:

    for i in range(N): f(N) (Choose the smallest correct estimate)

• A. N 中的线性
• B.在 N 中线性摊销
• C. N 的二次方
• D.根据给定的信息无法判断

假设 f(N) 只打印“Hello World”，所以它不依赖于参数有多大。我们可以说总运行时间在 N 中线性摊销吗？

Answer 1

这有点像测试题，所以我不只是说出答案，而是解释一下每个算法复杂性概念的含义。

让我们从一个声明开始函数 f(n) 在恒定时间内运行。我知道问题中甚至没有提到它，但它确实是理解所有其他算法复杂性的基础。如果某个函数以恒定时间运行，则意味着它的运行时间不依赖于它的输入参数。请注意，它可以像 print Hello World 或 return n 一样简单，也可以像找到前 1,000,000,000 个素数一样复杂(这显然需要一段时间，但需要的时间相同每次调用的时间量)。然而，最后一个例子更像是对数学符号的滥用；通常常数时间函数很快。

现在，如果一个函数 f(n) 以摊销常数时间运行，这意味着什么？这意味着如果您调用该函数一次，则无法保证它会以多快的速度完成；但是如果你调用它 n 次，花费的时间总和将是 O(n)(因此，平均每次调用花费 O(1))。 Here是来自另一个 StackOverflow 答案的较长解释。我想不出任何在分摊常数时间(但不是常数时间)内运行的极其简单的函数，但这是一个重要的例子:

called = 0
next_heavy = 1
def f(n):
  called += 1
  if called == next_heavy:
    for i in range(n):
      print i
    next_heavy *= 2 

在第 512 次调用时，此函数将打印 512 个数字；然而，在此之前它总共只打印了 511 次，所以它的打印总数是 2*n-1，也就是 O(n)。 (为什么是 511？因为从 1 到 2^k 的两个幂的和等于 2^(k+1)。)

请注意，每个常数时间函数也是一个摊销的常数时间函数，因为它需要 O(n) 时间来调用 n。因此，非摊销的复杂性比摊销的复杂性要严格一些。

现在你的问题提到了一个具有摊销对数时间的函数，这与上面类似意味着在 n 调用此函数后，总运行时间为 O(nlogn) (每次调用的平均运行时间为 O(logn))。然后，对于每个问题，这个函数在从 1 到 N 的循环中被调用，我们刚刚说过，根据定义，这些 N 调用将在 O 中运行(NlogN)。这是 linearithmic .

关于你问题的第二部分，你能根据我们之前的观察推断出循环的总运行时间是多少吗？