java - 该算法最坏情况下的时间复杂度是多少？

Question

算法如下:

boolean findTripleA(int[] anArray) { 
    if (anArray.length <= 2) { 
        return false; 
    } 

    for (int i=0; i < anArray.length; i++) { 
        // check if anArray[i] occurs at least three times 
        // by counting how often it occurs in anArray 

        int count = 0; 

        for (int j = 0; j < anArray.length; j++) { 
            if (anArray[i] == anArray[j]) { 
                count++; 
            } 
        } 

        if (count >= 3) { 
            return true; 
        } 
    } 

    return false;
}

该算法旨在确定一个数组是否包含至少一个数字在数组中出现三次或更多次。我的工作是找出这个数组的最坏情况及其时间复杂度。

我的想法是，最坏的情况是算法的每个条目出现两次(如果数组的元素数量为奇数，则额外的条目是唯一的)。在这种情况下，if for (int j = 0; j < anArray.length; j++)内的声明每次通过数组总是违反两次，迫使计算执行两次，但算法实际上并没有终止，直到它检查了每个元素。我在想这会有一个时间复杂度 O(n^2) .

任何人都可以提供对此的任何见解吗？因为我一直怀疑我是不正确的，如果我是，我想找出正确的答案以及为什么它是正确的。

Answer 1

最坏的情况是 O(N^2)，当您找不到三元组时就会发生这种情况。