2

我已经解决了运行时间为 Θ(2^n)、指数时间的递归关系。对于相同的递归关系，我如何找到 Ω 和 O。

我想如果它是 Θ(2^n)，它也应该是 O(2^n)，对吗？我如何找到 Ω 的下限？

我尝试解决递归关系：

T(n) = 2T(n-1) + C。

4

2 回答 2

5

如果一个函数是 Θ(f(n)) 这意味着它既是 O(f(n)) 又是 Ω(f(n))

反之亦然，如果一个函数既是 O(f(n)) 又是 Ω(f(n))，那么它是 Θ(f(n))

证明很简单：

g(n)=Θ(f(n)) => exists n0, c1 and c2 such that: c1f(n)<g(n)<c2f(n) for n>n0

只取前半部分：

exists n0 and c1 such that: c1f(n)<g(n) for n>n0 => g(n)=Ω(f(n))

下半场：

exists n0 and c2 such that: g(n)<c2f(n) for n>n0 => g(n)=O(f(n))

逆证明类似。

编辑：稍微了解一下 Θ、O 和 Ω 的含义。

您一定已经看过 Θ、O 和 Ω 的定义（如果没有，我刚刚在上面的证明中提到了这三个）。

那么除了它们的数学定义之外，它们的含义是什么？

基本上，这样想它们：

  • g(n) = O(f(n))这意味着当n变大时，f(n)总是具有比 更大的值g(n)。更准确地说，不是f(n)它本身，而是它的常数倍。例如，n+100是O(n^2)，因为对于n>10，1*n^2>n+100。此外，对于n>3, 11*n^2>n+100。所有这些符号的事情是，常数并不起重要作用，因为它f(n)决定了函数的增长方式。请注意，O 表示法显示了函数的上限，因此不是唯一的。例如 if f(n)=O(n), then it is also O(n^2)and O(nlogn)etc, but (may) notO(sqrt(n))

  • g(n) = Ω(f(n))这正是 O 的倒数。因此，它表明它是（再次乘以常数因子）f(n)的下限，并且它不是唯一的。g(n)例如 if f(n)=Ω(n), then 也是Ω(1)and Ω(1/n)。你总是有

    g(n) = Ω(f(n)) <=> f(n) = O(g(n))

  • g(n) = Θ((f(n))这是对您的功能增长的严格限制。它基本上意味着g(n)与 具有相同的增长f(n)，尽管它可能不如f(n). 这并不像Θ 所做的那样平滑：你有一个算法，其执行时间不是简单地表达的，但你可以用 Θ 分析它。f(n)g(n) = Θ((f(n))是这样的图片：

    |                     ---- 2*f(n)
|                    /    /\  ---(g(n)
|                ----    /  \/    -------- f(n)
|               /       /        /
|           ----   /\  / --------
|          /  -----  \/ /
|      ----  /  --------
|     /     /  /
| ---- --------
|/    /
+---------------------------------------------

有趣的事实：

  • f(n) = O(f(n))因为你有所有n, 2*f(n)>f(n)（2 是一个例子，任何大于 1 的常数都是好的）。函数的最小上界，就是函数本身！
  • 同样，f(n) = Ω(f(n))和f(n) = Θ(f(n))。此外，函数的最大下限是函数本身。
  • Θ 显示了函数的确切增长，如果您为您的算法找到它，那么它就是最好的描述。然而，许多算法具有复杂的行为，或者充其量根据它们的输入具有不同的增长（例如，插入排序Θ(n)给定一个已排序的输入并Θ(n^2)给定一个反向排序的输入）因此，并不总是可能找到算法的 Θ。
  • O 表示函数执行的上限。通常这是人们为他们的算法计算的。通过这样做，他们是在说，无论如何，我的算法并不比这差，但在某些情况下它可能会更好。例如，插入排序是O(n^2).
  • 有时 O 没有显示最佳（最小）上限，因为找到它太难了。在这些情况下，O 仍然会来救援。例如，如果您有一个算法可以在 UI 应用程序中处理大小为 1000 的输入（例如延迟 0.5 秒就可以了），那么如果您的算法是O(n^2)好的，那么即使算法的最坏情况执行是实际上低于那个（但你很难找到它）。最佳上限是算法最坏情况执行的增长率。在插入排序的示例中，最坏情况的执行是Θ(n^2)，因此，您可以为算法提供的最佳上限是O(n^2)（与O(n^3)示例相反）。
  • Ω 在实践中并不是那么有用，你永远不想说我的算法充其量是这样的，但可能更糟（那是糟糕的广告）！但是，在计算机科学中它非常有用。大多数时候，为了证明某事无法以更好的方式完成。例如，如果有一种算法解决了 中的问题Θ(n^3)，并且您证明无论解决问题的算法必须是什么Ω(n^3)，那么这意味着永远不会有比您已经拥有的算法更好的算法（所以您有点告诉其他人不要不找它，你不会找到它）

有很多 O-notation 数学不难理解或发明自己。一些例子是：

  • O(f(n)+g(n)) = O(max(f(n),g(n)))
  • O(f(n))+O(g(n)) = O(f(n)+g(n))
  • O(f(n))O(g(n)) = O(f(n)g(n))
  • O(cf(n)) = O(f(n)) 其中 c 是一个常数

您可以通过将它们放入 O 表示法的定义中来立即证明其中的大部分。

这些规则中的第一个可能是最有用的。如果你的算法有两个部分，一个将一些大小数组设置n为零，然后做一些事情，O(nlogn)那么总体顺序O(n+nlogn)就是简单的O(nlogn).

这意味着从数学上讲，拥有一千个O(nlogn)预处理和O(nlogn)解决问题的算法比拥有一个简洁的算法要好O(n^1.5)。请注意，在实践中，它不一定更好。你为什么问？第一个是O(nlogn)第二个，O(n^1.5)所以你说第一个更好？请记住，O 符号渐近地显示函数的行为。这意味着，是的，如果您的输出变得非常非常大，第一个算法（具有一千个预处理的算法）会更好，但在您的实际范围内n，1000nlogn可能比n^1.5.

于 2011-10-09T18:58:12.847 回答
4

如果是家庭作业，您可以尝试将其绘制为递归树，其中节点表示函数调用所需的操作的复杂性。

编辑：关于下限，欧米茄被定义为下限。如果你有 Theta（确切的行为），你也有 Omicron 和 Omega ......它们只是不太精确。

所以

Theta(n) <=> O(n) AND Omega(n)

剧透

如果我没记错的话，你是这样理解的……

你有一棵树，在它的根部你只有C（处理解决方案的工作），你必须在两个分支中吐出（再次C作为工作），节点得到分支n时间

     C
    /|
   C C
  /| |\
 C C C C
/| ......

完整的解决方案

因为树的深度为n，在底部你有2^n所有复杂度为 的节点C，那么你有复杂度的n-1级别C, 2C, 4C....(2(n-1)*C)，它们应该总结为2^n*c

所以最终的复杂性应该2*(2^n)*C是theta(2^n)

于 2011-10-09T18:47:30.460 回答