if在for循环内的时间复杂度

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)表示。