algorithm - 最佳运行时间

Question

使用 theta 表示法的最佳运行时间是多少:

1. 在排序数组中查找一个元素
2. 在已排序的链表中查找元素
3. 一旦找到位置，就在排序数组中插入一个元素
4. 一旦找到位置，就在排序的链表中插入一个元素

到目前为止，我有 2) 是 theta(n) 和 4) 是 theta(1) 只是因为我记得我的教授刚刚在类里面说过答案，但是有关于如何得到这些的解释吗？

Answer 1

首先阅读您的一个答案，您似乎在要求 O[big o] 中的复杂性。当复杂性在上方和下方渐进地绑定(bind)时，使用 Theta 表示法。大 O 表示法适用于复杂度渐近约束的情况，仅在上面。

<强>1。在排序数组中查找元素:

使用二进制搜索，它可以是 O(logn)。但在最好的情况下 Ω(1)

<强>2。在排序链表中查找元素

你不能在这里使用二进制搜索。您必须遍历整个列表才能找到特定的数字。如果不遍历它之前(或之后)的数字，就无法到达特定位置。所以在最坏的情况下，你遍历 n(length) 次。所以 O(n)

Ω(1)，因为在最好的情况下，您可以在开头找到它。

<强>3。一旦找到位置，就在排序数组中插入一个元素

O(n) 因为你必须将所有数字移动到新插入位置的右侧。

Ω(1)，因为在最好的情况下，您可能会在最后添加它。

<强>4。一旦找到位置，就在排序的链表中插入一个元素

Ɵ(1) O(1) Ω(1)，因为在特定位置添加新元素(在您知道该位置并且您有指向该位置的指针之后)是 theta(1)