Geek asks and answers

What is the complexity for i: for o = i + 1

for i = 0 to size(arr)
   for o = i + 1 to size(arr)
      do stuff here

What is the worst difficulty of this? This is not N ^ 2, because the second decreases by one every cycle. This is not N, it should be more. N-1 + N-2 + N-3 + ... + NN + 1.

0
source share
4 answers

is he N ^ 2, since it is a product of two linear difficulties.

(There is a reason why asymptotic complexity is called asymptotic rather than identical ...)

See Wikipedia for simplified solutions .

+9
source

Think of it as if you are working with an nxn matrix. You are approximately working on half the elements in the matrix, but O (n ^ 2/2) is the same as O (n ^ 2).

+2

n*(n-1)/2, O(n^2).

+1

, , , . , f(n)=n^2-10000*n+400, O(f(n)), " " . ? n , . , , f1(n)=n^2-n-4, f2(n)=n^2 O(n^2). , n .

, n=size(arr), do stuff here f(n)=n+(n-1)+(n-2)+...+2+1 . , f(n) , f(n)=n*(n+1)/2, .. f(n)=0.5*n^2+0.5*n. , do stuff here - O(1), O(n^2).

= 0 (arr)

, , i size(arr), . , , f(n)=0.5*n^2-0.5*n, O(n^2). , O(1),O(n),0(n^2),... , - , n .

+1

More articles:


All Articles