我有一份考试前要做的练习 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 次的数字。
谢谢大家
最佳答案
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|2) = O(n2).
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))。
关于arrays - 降低数组中最大重复元素的复杂性,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/36286588/