algorithm - 如何计算大 O 表示法中的时间复杂度以进行数组双重查找

Question

以下算法的时间复杂度是多少？？有人可以帮忙吗

public class Util
{

    public static int GetDistance(int[] array)
    {
        //Find the max seperation of two same numbers inside an array for example 
        // {1,2,4,1,5,9,0,4,15,1,2} should return 9 ( position of '1' at 9th and 0th location)

        int N = array.Length;
        int maxDistance=0;
        for (int i = 0; i < N; i++)
        {
            for (int j = (N-1); j > i; j--) 
             {
                 if (array[j]==array[i])   
                    if(maxDistance < (j-i))
                        maxDistance = j- i;
             }//End of inner for

        }//End of for
        System.Console.WriteLine("maxDistance " + maxDistance);
        return maxDistance ;
    } //End of Function

} //End of Class

Answer 1

你看内层循环(内层循环里面的操作需要常数时间)。内部循环恰好执行 N-1-i 次。

然后外层循环恰好执行 N 次，i 的值增加。总工作量涉及

(N-1) + (N-2) + (N-3) + ... + 1

内部 body 的处决。这个和是一个三角数，证明等于没什么大不了

(N-1).N / 2

这是 O(N²)。