最佳運行時間

Question

什麼是藉助THETA符號的最佳運行時間爲：

1. 查找有序數組
2. 元素查找有序鏈表
3. 的元素在排序中插入元素陣列，一旦位置被發現
4. 插入在一個有序鏈表的元素，一旦位置被發現

到目前爲止I H ave 2）是theta（n），4）是theta（1），因爲我記得我的教授剛剛在課堂上說了答案，但是有沒有解釋如何得到這些答案？

Answer 1

首先閱讀你的一個答案，似乎你可能會要求O [大o]中的複雜性。當複雜度在上下都漸近地漸近時，就會使用這個表示法。大O符號表示當複雜性漸近時，僅在上面。

1.查找排序後的數組的元素：

使用二進制搜索它可以是O（logn）時間。但是，在最好的情況Ω（1）

2.查找有序鏈表

元素你不能在這裏使用二進制搜索。你必須遍歷整個列表才能找到一個特定的號碼。如果沒有在之前（或之後）遍歷數字，沒有辦法進入特定的位置。所以在最壞的情況下，你會遍歷n（長度）次。所以O（n）

Ω（1），因爲在最好的情況下，你可以在開始時找到它。

3.在排序後的數組插入的元件，一旦位置被發現

爲O（n），因爲你必須所有的數字轉移到新插入的地方的位置的右​​側。 （1）因爲在最好的情況下，你可能會在最後加上它。

4.插入在一個有序鏈表的元素，一旦位置被發現

Ɵ（1）O（1）Ω（1），因爲在特定位置添加新元素（後你知道這個位置，並且你有一個指向該位置的指針）是theta（1）