arrays - 降低数组中最大重复元素的复杂性

Question

我有一份考试前要做的练习 list ，它们没有评分，所以我没有将它们标记为家庭作业。

算法采用数字数组

给定这个算法:

         Algo-X(A)
                i=1 
                j=1  
                m=0 
                c=0
                while i ≤ |A|
                    if A[i] == A[j]
                        c=c+1 
                    j=j+1
                    if j > |A|
                        if c > m
                           m=c 
                        c=0
                        i=i+1
                        j=i 
                return m

问题一:分析Algo-X的复杂度。

问题 2:编写一个算法，其功能与 Algo-X 完全相同，但性能更优渐近时间复杂度。

现在，这个的时间复杂度是 O(n^2) 对吧？

根据我的理解，算法本身在数组内搜索并返回数组内最大重复数的数字。

如何降低复杂性？

我不能假设存在 N/2 次的数字。

谢谢大家

Answer 1

Now, the time complexity of this is O(n^2) right?

是的，你是对的。 j将遍历 i 中的所有元素至 |A|对于每个 i来自 1至 |A| .

∑_{i = 1..|A|}∑_{j = i..|A|}(j) = O(|A|²) = O(n²).

How can I reduce the complexity?

您可以先对初始数组进行排序。然后所有相等的数字将依次出现。您只需寻找最长的一组相等元素。

sort(A)
m = 1
c = 1
i = 2
while i ≤ |A|
    if A[i] == A[i - 1]
        c = c + 1
    else 
        c = 1
    if c > m
        m = c
    i = i + 1

排序的时间复杂度为 O(n * log(n))，处理排序数组的时间复杂度为 O(n)。总时间复杂度为 O(n * log(n))。