java - 以下对于 Largest in array of unsorted numbers 的时间复杂度

Question

谁能帮忙分析一下这个can的时间复杂度，请解释原因。 我正在将数组元素相互比较，其中一个是最大值。 我不确定如何为此计算时间复杂度。 谁能帮我解决这个问题？

 class Largest
 {
     public static void main (String[] args) 
  {
    int array[] = {33,55,13,46,87,42,10,34};
    int max = array[0]; // Assume array[0] to be the max for time-being

    for( int i = 1; i < array.length; i++) // Iterate through the First Index and compare with max
    {
        if( max < array[i])
        {
            max = array[i];
        }
    }
    System.out.println("Largest is: "+ max);
 }
}

Answer 1

它是O(n)

//loop n-1 times, O(n)
for( int i = 1; i < array.length; i++) // Iterate through the First Index and compare with max
{
    //one comparison operation, O(1)
    if( max < array[i])
    {
        //one assignment operation, O(1)
        max = array[i];
    }
}

你做了 2 个常量操作，n-1 次。

O(n) * [O(1) + O(1)] = O(n)