有没有big O和big theta不同的算法？
Is there any algorithm whose big O and big theta are different?
有没有big O和big theta不同的算法？我发现它们非常相似，同时又令人困惑。
我认为这里的部分混淆源于 算法 没有 "a big-O" 或 "a big-Theta." 使用 O 和 Θ 符号来描述功能的长期增长率，而不是算法。当您听到有人说 "binary search is O(log n)," 之类的话时，他们真正在说的是 "the runtime of binary search is O(log n)" 或 "the worst-case runtime of binary search on an input of length n is O(log n)."
另一个可能造成混淆的原因是一个函数可以是多个不同函数的大 O。例如函数f(n) = n是O(n)，但也是O(n2)，O(n3 ), O(2n), 等。这源于 big-O 符号的正式定义，它表示 f(n) = O(g(n)) 如果（直观地) 在长期内，f(n) 受 g(n) 的某个常数倍数的限制。这意味着我们不一定要谈论某些函数运行时的 "the" big-O，因为可能有无限多的函数可能符合要求。
我们可以这样说：如果一个函数的运行时间是Θ(f(n))，那么这个函数的运行时间也是O(f(n))。这是根据 Θ 符号的定义得出的。另一方面，反之亦然。如果一个函数的运行时间为 O(f(n))，则该函数的运行时间不一定是 Θ(f(n))。我们可以使用像二分查找这样的东西作为例子——二分查找运行时间为 O(log n)，但它的运行时间也是 O(n) 和 O(n2)，因为它们是较弱的边界。但是，二分查找的运行时间不是Θ(n)，也不是Θ(n2)或Θ(2n)。
你可以将大 O 视为渐近上界。渐近下界有一个很大的 Omega。
如果大 O 和大 Omega 相同，则在大 Theta 中。
例如，您可以考虑一种算法来找到长度为 n 的无序序列中的最大数。该算法非常简单，它检查数字并将当前最大值存储在变量中。在最坏的情况下，你必须检查序列中的每个值（它是无序的，最大值在最后）如此大的 Omega = n。现在你可以考虑一个上限，它也可以是 n。但是例如 n 平方也是一个有效的上限或 n！等等
有没有big O和big theta不同的算法？我发现它们非常相似，同时又令人困惑。
我认为这里的部分混淆源于 算法 没有 "a big-O" 或 "a big-Theta." 使用 O 和 Θ 符号来描述功能的长期增长率，而不是算法。当您听到有人说 "binary search is O(log n)," 之类的话时，他们真正在说的是 "the runtime of binary search is O(log n)" 或 "the worst-case runtime of binary search on an input of length n is O(log n)."
另一个可能造成混淆的原因是一个函数可以是多个不同函数的大 O。例如函数f(n) = n是O(n)，但也是O(n2)，O(n3 ), O(2n), 等。这源于 big-O 符号的正式定义，它表示 f(n) = O(g(n)) 如果（直观地) 在长期内，f(n) 受 g(n) 的某个常数倍数的限制。这意味着我们不一定要谈论某些函数运行时的 "the" big-O，因为可能有无限多的函数可能符合要求。
我们可以这样说：如果一个函数的运行时间是Θ(f(n))，那么这个函数的运行时间也是O(f(n))。这是根据 Θ 符号的定义得出的。另一方面，反之亦然。如果一个函数的运行时间为 O(f(n))，则该函数的运行时间不一定是 Θ(f(n))。我们可以使用像二分查找这样的东西作为例子——二分查找运行时间为 O(log n)，但它的运行时间也是 O(n) 和 O(n2)，因为它们是较弱的边界。但是，二分查找的运行时间不是Θ(n)，也不是Θ(n2)或Θ(2n)。
你可以将大 O 视为渐近上界。渐近下界有一个很大的 Omega。
如果大 O 和大 Omega 相同，则在大 Theta 中。
例如，您可以考虑一种算法来找到长度为 n 的无序序列中的最大数。该算法非常简单，它检查数字并将当前最大值存储在变量中。在最坏的情况下，你必须检查序列中的每个值（它是无序的，最大值在最后）如此大的 Omega = n。现在你可以考虑一个上限，它也可以是 n。但是例如 n 平方也是一个有效的上限或 n！等等