嗨，我不知道計算復雜性。因此，如果有人幫助我找到答案，那就太好了。（也試著寫下你是如何計算的）
找出以下演算法的復雜度：
function min (X1, X2…………Xn)
min = X1;
for i = 2 to n
if (min > Xi) then
min = Xi;
uj5u.com熱心網友回復：
讓我們從時間開始：
function min (X1, X2…………Xn)
min = X1; # const_1
for i = 2 to n # n - 1 times
if (min > Xi) then # const_2
min = Xi; # const_1 (if min > Xi), 0 (if min <= Xi)
因此，對于最壞的（X1..Xn按降序排序時）情況，我們有執行時間T
T = const_1 (n - 1) * (const_2 const_1)
對于最好的情況（什么時候X1是最小值）
T = const_1 (n - 1) * (const_2)
我們可以將這些案例結合在一起，并有
T = const_1 (n - 1) * (const_2 p * const_1)
where p - some value in 0..1 range (0 - best, 1 - worst case)
在任何情況下，我們都有一個執行時間的線性公式T
T = A n * B
whereA和B一些常量值。或者對于復雜性 O(T)：
O(T) = O(A n * B) = O(A) O(B * n) = O(B * n) = B * O(n) = O(n)
轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/395986.html