最佳运行时间

Question

使用θ表示法的最佳运行时间是什么：

1. 在排序数组中查找元素
2. 在排序链接列表中查找元素
3. 找到位置后，将元素插入排序数组中
4. 找到位置后，将元素插入排序链接列表中

到目前为止，我有θ(N)和θ(1)仅仅是因为我记得我的教授刚才在课堂上说的答案，但是对于如何得到这些有解释吗？

Answer 1

首先，阅读您的答案之一，似乎您可能要求复杂性在Obig o.Theta表示法是使用时，复杂性是渐进的，无论是在上面和下面。大O表示法是用来表示当复杂度渐近地有界时，只有在上面。

1.在排序数组中找到一个元素：

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

2.在排序链接列表中找到一个元素

你不能在这里使用二进制搜索。你必须遍历整个列表才能找到一个特定的数字。没有办法去一个特定的位置，而不遍历数字之前(或之后)它。所以在最坏的情况下，你遍历n(长度)次。所以O(n)

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

3.在排序数组中插入元素，一旦找到位置

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

Ω(1)，因为在最好的情况下，您可能只是在末尾添加它。

4.在找到位置后，在排序链接列表中插入一个元素

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