큰 O - O (N^2) 또는 O (N^2 + 1)?

내가 읽고있는 것 this 내 알고리즘에 어떤 변화가 영향을 주는지 알아 내려고하는 Big O 기사 (및 다른 책 참고서). 큰 O - O (N^2) 또는 O (N^2 + 1)?

bool ContainsDuplicates(String[] strings) 
{ 
    for(int i = 0; i < strings.Length; i++) 
    { 
     for(int j = 0; j < strings.Length; j++) 
     { 
      if(i == j) // Don't compare with self 
      { 
       continue; 
      } 

      if(strings[i] == strings[j]) 
      { 
       return true; 
      } 
     } 
    } 
    return false; 
}

나는 다음과 같이 변경했다 :

때문에 (N^2) 코드를 다음 O를 제공

bool ContainsDuplicates(String[] strings) 
{ 
    for(int i = 0; i < strings.Length; i++) 
    { 
     for(int j = 0; j < strings.Length; j++) 
     { 
      if(i != j) // Don't compare with self 
      {        

        if(strings[i] == strings[j]) 
        { 
         return true; 
        } 
      } 
     } 
    } 
    return false; 
}

지금 모두 IF의 중첩하고 '계속'는 제거됩니다. 이 알고리즘이 실제로 O (N^2 + 1)이 되었습니까? 그리고 왜 ? IF 체크가 무의식 전에 존재했기 때문에 처음에는 여전히 O (N^2)라고 생각했습니다.

출처

2013-12-14 Fawix

큰 오 표기법에서는 상수가 포함되지 않기 때문에 (* 점근 적 복잡도 ** ** 동일한 복잡도가 아니기 때문에) 'O (N^2 + 1)'과 같은 것은 없습니다. –

은 런타임과 복잡도가 동일하다는 것을 의미합니까? 두 함수 모두 O (N^2)입니까? – Fawix

N² *가 * 1을 지배하므로 O (N² + 1)은 O (N²)와 동일합니다. – dkrikun

Big O는 선택한 매개 변수가 커짐에 따라 실행 시간이 어떻게 증가 하는지를 설명합니다.

시간 촬영 = 시간 (시작) + 시간 (외부 루프) * N + 시간 (계속) * N + 시간 : 우리가 정확하기를 원한다면 당신의 예에서

, 공식은 것 (NO 계속) * N^2 재기록 가능

시간 촬영

같이 = A + B * N + C * N^2

이제 N이 커지면 전체적으로 포물선처럼 보일 것입니다. N이 무한대로 증가함에 따라 차수 0과 차수 1 항은 무의미 해집니다.

시간 촬영 (대 N) ~ = C를 * N^2 우리 질적 정량적하지 논의 관련 보낸 마지막

, 우리는 단지 N로 algorirhm를 설명^2

O (N^2) 알고리즘

0 N
큰 값의 C * N^2의 대략 동작한다는 것을 의미
이것은 미적분학에서 o (x)와 유사한 개념입니다 (small-o는 매개 변수가 0 인 차이입니다).

출처

2013-12-14 15:28:18 Sklivvz

좋습니다! 지금 나는 마침내 더 큰 N 만이 고려되는 이유를 얻습니다! 질적으로, 내 X 축에 +1이 있다고해서 그것이 내 런타임에 추가되었다는 것을 의미하지는 않습니다. – Fawix

@Fawix는 양적 값이 알고리즘을 실행하는 컴퓨터에 따라 다르지만 O 클래스는 독립적이라는 것을 명심하십시오. – Sklivvz

큰 O - O (N^2) 또는 O (N^2 + 1)?

답변

관련 문제