我目前正在大學學習演算法單元，我似乎無法從任何人那里得到關于確定演算法基本操作的明確答案。我知道它可能發生在多個地方，但是在考慮最佳情況、平均情況和最壞情況時會有所不同嗎？
在下面的示例中，我是否正確假設 A[i] = Null 是最佳情況的基本操作，因為它是提供最佳執行時間的操作？
并且 A[i] = 0 是最壞情況下的基本操作，因為它的代碼塊將具有最長的執行時間？平均情況如何？會是與陣列的所有 4 個比較嗎？就像我說的，我似乎無法從任何人那里得到明確的答案。甚至我讀過的教科書也非常模糊。任何幫助將不勝感激。
for i <- 0 to n-1
if A[i] = Null
return
else
if A[i] < 0
.....
.....
.....
else if A[i] = 0
for j <- 0 to n-1
.....
.....
.....
else if A[i] > 0
.....
.....
.....
uj5u.com熱心網友回復：
O表示法是一個表示執行時間的函式，也就是時間復雜度。隨著輸入大小n的增加，一項將成為主導項。這個主導項所代表的操作就是所謂的基本操作。
假設您示例中的所有點都是O(1)這些點是您的基本操作。
- 如果
a[0] == null最好的情況是O(1)（不是真正的情況，因為它似乎代表丟失的資料）。 - 如果
a[i] == 0每個i最壞的情況復雜度是O(n^2)。 - 如果 case
a[i]是每個i的隨機值，則平均情況將為O(n)（盡管某些值包含零并且平均情況可能略高于O(n)）
uj5u.com熱心網友回復：
支配演算法性能的操作有時稱為基本操作。在您的示例中，它是對 A[i] 的評估。根據 n 次迭代的結果，演算法性能會有所不同。通過指定三個極端情況（最佳、最差和平均）來捕獲頻率如何。在這里，它取決于 A[i] 評估為零的頻率 - 從不、總是或平均（假設某些分布）。性能案例通常（但不一定）使用大 O 表示法指定。
所以基本操作設定性能，三個性能案例表明它是如何發揮作用的。
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/489543.html