for循环内if的时间复杂度

Question

for(int i = 0; i < Array.length ;i++)
{
   ...
   if(s[i]>s[m]){
      m = i;
   }
}

这个算法的时间复杂度是多少？ O(n)?

Answer 1

for(int i = 0; i < Array.length ;i++)
{
  ...
  if(s[i]>s[m]){
      m = i;
   }
 }

n 数组的大小，并假设在“...”中完成的计算是恒定的，所以让我们将在“...”上花费的时间标记为c1，然后 if(s[i]>s[m]) 所用的时间为 c2， m = i 为 c3。在最坏的情况下，此代码的时间复杂度为：

n * (c1 + c2 + c3)

可以表示为O(n).

Time Complexity of if inside of for loop