Is the time complexity of a while loop with three pointers different than 3 nested for loops?
https://softwareengineering.stackexchange.com/questions/290170
-
09-10-2020 - |
Вопрос
This program (written in ruby) finds the largest 3 numbers in an array (without sorting the array). It has a while loop with three pointers. My fist instinct, since there is only one loop is to say this solution is O(n). But, the pointer's j and k get reset when they reach n which seems the same as using 3 for loops, so then is it O(n³)?
def greatest_of_3_with_ptrs(a)
greatest = 0
greatest_tuple = nil
i,j,k=0,1,2
n = a.length-1
while( true) do
sum = a[i]+a[j]+a[k]
if sum > greatest then
greatest = sum
greatest_tuple =[a[i],a[j],a[k]]
end
sum = 0
if k == n then
j=j+1
k=j+1
else
k+=1
end
if j == n then
i=i+1
j=i+1
k=j+1
end
break if k > n || j > n || i==n
end
{ greatest_tuple: greatest_tuple, greatest: greatest }
end
a =[10,-1,4,2,5,3,0]
expected = 19
print greatest_of_3_ptrs(a)[:greatest] #> 19
print greatest_of_3_ptrs(a)[:greatest_tuple] #> [10,4,5]
Please Note: I am aware of the O(n) solution, that is not my question
def greatest(a)
max_1,max_2,max_3 = a[0],a[1],a[2]
for i in 3..a.length-1
if a[i] > max_1 then
max_1 = a[i]
elsif a[i] > max_2 then
max_2 = a[i]
elsif a[i] > max_3 then
max_3 = a[i]
end
end
[max_1,max_2,max_3]
end
Решение
If looks like a O(n³) solution. Your instinct is correct: by resetting variables you are looping. Note: if we only consider the loop instruction we would, mistakenly, think it was O(∞).
However the problem is O(n). Therefore you can do better.
Другие советы
You are absolutely correct. The function tries out all possible combinations of elements from the array. In this case, it's O(n³) and would be of an even higher power, if you wrote a similiar function for the greatest 4, 5, .. elements. The best solution for any of these problems should be of the order O(n).
I just want to mention that in your example for an O(n) solution you omitted the "down-shift" when replacing a value:
def greatest(a)
max_1,max_2,max_3 = a[0..2].sort.reverse #changed
for i in 3..a.length-1
if a[i] > max_1 then
max_3 = max_2 #new
max_2 = max_1 #new
max_1 = a[i]
elsif a[i] > max_2 then
max_3 = max_2 #new
max_2 = a[i]
elsif a[i] > max_3 then
max_3 = a[i]
end
end
[max_1,max_2,max_3]
end