找出给定算法的复杂性

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

其中 A 和 B 一些常量值。或者对于 复杂性 O(T):

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

找出给定算法的复杂性

Finding the complexity of the given algorithm

algorithm

big-o