给定代码的时间复杂度是多少？

Question

import java.util.Scanner;


public class PairsOfElementsSumEqualsN {

    public static void main(String[] args) {
        // TODO Auto-generated method stub

        Scanner s  = new Scanner(System.in);

        System.out.println("enter the number");

        int n = s.nextInt();

        int[] array = new int[]{1,2,1,2,4,5,6,7,8,9};

        int j = 0;
        int i = 0;

        for(i = 0 ; i<array.length;i++)
        {
            for(j=i+1;j<array.length;j++)
            {
                if(array[i] + array[j] == n)
                {
                    System.out.println(array[i] + "," + array[j]);
                }

            }
        }

    }

}

我认为它应该是n ^ 2但我想要答案的解释

Answer 1

是的,你是对的它的时间复杂度是O(n ^ 2).

您在第一次传球中进行n-1次比较,在第二次传球中进行n-2次比赛,在第三次传球中进行n-3次比赛,依此类推.所以比较的总数将是.

(n-1)+(n-2)+(n-3)+.....+3+2+1
Sum = n(n-1)/2
i.e O(n^2)

这是因为big-O表示法描述了算法的本质.扩展(n-1)*(n-2)/ 2中的主要项是n ^ 2.因此,当n增加时,所有其他术语变得微不足道.