Absolute Differenz bei jedem Elemente des Arrays für jedes Element in der linearen Zeit

Question

einen Array

a[4]={2,5,8,9}; 

die absoluten Unterschiede in Bezug würde

(3,6,7,3,4,1) 
abs(2-5)=3 
abs(2-8)=6 
abs(2-9)=7 
abs(5-8)=3 
abs(5-9)=4 
abs(8-9)=1 

jedes Element sein Ist es möglich, diese zu finden in lineare Zeit? Wenn ja, wie?

Answer 1

Wenn n die Anzahl der Elemente ist, müssen Sie (n-1) + (n-2) + ... + 1 Vergleiche machen, und Sie können es offensichtlich tun, so dass es wie Theta aussieht (n^2) Vergleiche. Wenn du es in linearer Zeit machen könntest, wäre die Blasensortierung linear (es ist n^2).