查找给定算法的复杂性

Question

嗨，我不知道要计算复杂性。所以，如果有人帮我找到答案，那就太好了。(也试着写下你是如何计算的(

找出以下算法的复杂性：

function min (X1, X2…………Xn)
min = X1;
for i = 2 to n 
if (min > Xi) then 
min = Xi;

Answer 1

让我们从计时开始：

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

其中CCD_ 5和CCD_。或者对于复杂性O(T):

O(T) = O(A + n * B) = O(A) + O(B * n) = O(B * n) = B * O(n) = O(n)