컴퓨팅 알고리즘의 복잡성 - 혼란

Question

나는이 다음 코드 :

sum = 0; 
for (i = 0; i < n; i++) 
    for (j = 0; j < i; j++) 
     sum++; 

복잡성이 O(n^2) 것,하지만 내부 루프의 복잡성에 대한 좀 더 파고하려면 다음이 (n (n-1))/2 또는 (n-1)! 것입니까?

Answer 1

예, O (n^2)하지만 실제로 0 + 1 + ... + n-1 = n (n-1)/2 = O (n^2) !

Answer 2

big-O 표기법에 관한 한 상수는 부적절합니다.

Answer 3

계산 한 내용 (n(n-1)/2)은 코드에 대한 정확한 반복 횟수입니다. 시간 복잡성에 대해 큰 O가 요구되면, 시간을 표현하기에 충분한 크기의 추정치를 제공합니다. 즉

, 당신은 THE SMALLESTpowern의를 찾을 필요가 일부 k (k>0)를 들어, k * n^power는 반복의 정확한 숫자보다 클 것 같은. 귀하의 경우 k은 1이고 power은 2입니다. 다음 O(n^power) 귀하의 시간 복잡합니다. 큰 O 표기법 이후

Answer 4

time = n*(n-1)/2 
    = (n*n - n)/2 

은에 상한선을 나타내는 중요하지 않기 때문에 (모두 제거됩니다 상한, 적은 차 기간 (-n)와 상수 계수 (1/2)입니다 시간)을 사용하여 큰 -0 표기법을 생성합니다. O(n*n)은 O(n^2)으로 잘 알려져 있습니다.

Answer 5

우선, (n-1)!은 (n-1)(n-2)...(2)(1)을 의미합니다. 이것은 분명히 당신이 원하는 것이 아닙니다.

실제 반복 횟수를 계산하면 0 + 1 + 2 + ... + (n-2) + (n-1)이됩니다. 합계에 n 개의 용어가 있으며 각 쌍의 평균값이 (n-1)/2 인 방식으로 이들을 페어링 할 수 있습니다. (가장 높은 값과 가장 낮은 값, 두 번째 값과 두 번째 값이 낮은 값과 쌍을 이루는 값) n이 홀수 인 경우 남은 값은 쌍을 이룰 수 없지만 편리하게 값은 (n-1)/2입니다. 따라서 n 개의 용어가 있으며 모든 용어의 평균은 (n-1)/2이므로 총계는 n(n-1)/2입니다.

큰 O 표기법의 경우 정확히 얼마나 많은 반복이 필요한지 알 수 없습니다. n이 매우 큰 경우 한도를 알고 싶을뿐입니다. 반복 횟수는 (1/2)n^2 - (1/2)n으로 작성할 수 있습니다. n 매우 큰 경우 n^2 용어는 n 용어보다 길기 때문에 n 용어는 삭제됩니다. 그것은 우리에게 (1/2)n^2으로 남겨 둡니다. 그러나 큰 O 표기법의 또 다른 규칙은 우리가 상수 요소에 관심이 없기 때문에 그냥 O (n^2)라고 씁니다. (n은^2)

Answer 6

당신은 시간

22222222222222 + 4444444444444*n + 9999999999999999999999999*n^2 steps

에서 실행되는 알고리즘을 가질 수 그리고 그것은 여전히 ​​O를 될 것입니다.

알고리즘 실행 시간이 O보다 나은 이유는 공개 된 문제입니다.