了解 Big-Ω (Big-Omega) 符号
Understanding Big-Ω (Big-Omega) notation
我正在阅读一些关于算法 运行 时间的对数和增长率的资料。
但是，我在理解 Big-Ω (Big-Omega) 符号时遇到了问题。
我知道我们将它用于 'asymptotic lower bounds'，并且我们可以表达算法需要 至少一定时间 .
考虑这个例子：
var a = [1,2,3,4,5,6,7,8,9,10];
有人选了一个号码。我编写了一个程序，尝试使用线性搜索（1、2、3、4 ... 直到它猜到数字）来猜测这个数字。
我可以说算法的 运行 时间将是 其输入大小的函数 ，所以这些都是正确的（n是数组中元素的数量):
- Θ(n)（Big-Theta 符号 - 渐近紧界）
- O(n)（大 O 表示法 - 上限）
当谈到 Big-Ω 时，根据我的理解，算法的 运行 时间将是 Ω(1)，因为它是找到所选数字所需的最少猜测次数（例如，如果, 玩家选择了 1 (数组中的第一项))。
我认为这是因为这是我在 KhanAcademy:
上找到的定义
Sometimes, we want to say that an algorithm takes at least a certain
amount of time, without providing an upper bound. We use big-Ω
notation; that's the Greek letter "omega."
我说这个算法的 运行 时间是 Ω(1) 对吗？它也是 Ω(n)，如果是 - 为什么？
大 O、Theta 或 Omega 表示法都指的是解决方案如何随着问题的规模趋于无穷大而渐近扩展，但是，它们确实应该以您正在测量的内容开头。
通常当谈到大 O(n) 时，通常意味着 最坏情况复杂度 是 O(n)，但是，有时确实会看到它用于 典型 运行 次，特别是对于具有随机元素或根本不能严格保证收敛的启发式或算法。
所以这里，我们大概说的是最坏情况下的复杂度，也就是Theta(n)，既然是Theta(n)，那么它也是O(n)和Omega(n)。
证明下限未知的一种方法是说 X 是该算法的最简单情况，这里最好的情况是 O(1)，因此我们可以说该算法至少采用 Omega (1) 并且至多为 O(n)，Theta 未知，这是正确的用法，但目的是获得 Omega 的最高可能界限，这仍然是正确的，以及 O(n) 的最低可能界限，这仍然是真的。这里 Omega(n) 很明显，所以说 Omega(n) 比 Omega(1) 更好，就像说 O(n) 而不是 O(n^2) 一样。
我正在阅读一些关于算法 运行 时间的对数和增长率的资料。
但是，我在理解 Big-Ω (Big-Omega) 符号时遇到了问题。
我知道我们将它用于 'asymptotic lower bounds'，并且我们可以表达算法需要 至少一定时间 .
考虑这个例子：
var a = [1,2,3,4,5,6,7,8,9,10];
有人选了一个号码。我编写了一个程序，尝试使用线性搜索（1、2、3、4 ... 直到它猜到数字）来猜测这个数字。
我可以说算法的 运行 时间将是 其输入大小的函数 ，所以这些都是正确的（n是数组中元素的数量):
- Θ(n)（Big-Theta 符号 - 渐近紧界）
- O(n)（大 O 表示法 - 上限）
当谈到 Big-Ω 时，根据我的理解，算法的 运行 时间将是 Ω(1)，因为它是找到所选数字所需的最少猜测次数（例如，如果, 玩家选择了 1 (数组中的第一项))。
我认为这是因为这是我在 KhanAcademy:
上找到的定义Sometimes, we want to say that an algorithm takes at least a certain amount of time, without providing an upper bound. We use big-Ω notation; that's the Greek letter "omega."
我说这个算法的 运行 时间是 Ω(1) 对吗？它也是 Ω(n)，如果是 - 为什么？
大 O、Theta 或 Omega 表示法都指的是解决方案如何随着问题的规模趋于无穷大而渐近扩展，但是，它们确实应该以您正在测量的内容开头。
通常当谈到大 O(n) 时，通常意味着 最坏情况复杂度 是 O(n)，但是，有时确实会看到它用于 典型 运行 次，特别是对于具有随机元素或根本不能严格保证收敛的启发式或算法。
所以这里，我们大概说的是最坏情况下的复杂度，也就是Theta(n)，既然是Theta(n)，那么它也是O(n)和Omega(n)。
证明下限未知的一种方法是说 X 是该算法的最简单情况，这里最好的情况是 O(1)，因此我们可以说该算法至少采用 Omega (1) 并且至多为 O(n)，Theta 未知，这是正确的用法，但目的是获得 Omega 的最高可能界限，这仍然是正确的，以及 O(n) 的最低可能界限，这仍然是真的。这里 Omega(n) 很明显，所以说 Omega(n) 比 Omega(1) 更好，就像说 O(n) 而不是 O(n^2) 一样。