이해하는데 도움이 필요합니다. Big-O

Question

저는 데이터 구조 클래스에 속해 있으며 알고리즘 분석의 수단으로 Big-O를 다루고 있습니다. 불행히도 많은 시간을 공부 한 후에도 여전히 다소 혼란 스럽습니다. Big-O가 무엇인지 알고 있으며, 온라인에서 발견 된 몇 가지 좋은 코드 예제를 이해합니다. 그러나 나는 이해하지 못하는 숙제 문제를 가지고있다. 다음에 대한 설명은 크게 감사하겠습니다.

각각에서 출력 명령문이 몇 번 실행되는지 결정합니다 (n으로 숫자 지정). 그런 다음, 알고리즘 (N) O 또는 O (N2)인지 여부를 나타내는 :

for (int i = 0; i < n; i++) 
     for (int j = 0; j < i; j++) 
      if (j % i == 0) 
       System.out.println(i + ” ” + j); 

Answer 1

n = 5라고 가정하면 i의 값은 0, 1, 2, 3 및 4가됩니다. 이는 내부 루프가 1, 2, 3, 4 및 5 번 반복한다는 것을 의미합니다. 각기. 이 때문에 if 비교가 실행할 총 횟수는 1 + 2 + 3 + 4 + 5입니다. 1에서 n까지의 정수의 합계에 대한 수학 공식은 n * (n + 1)/2입니다. Expanded, 이것은 n^2/2 + n/2를 제공합니다.
따라서 알고리즘 자체는 O (n^2)입니다.

무언가가 인쇄되는 횟수에 대해 j % i = 0 인 시간을 조사해야합니다. j가일 때, 이것이 사실 일 수있는 유일한 시간은 j = 0 일 때이므로, 이것은 j = 0이고 i가 0이 아닌 횟수입니다. 이것은 바깥 쪽의 각 반복에서 한 번만 true라는 것을 의미합니다 루프, 첫 번째 반복을 제외하고 (i = 0 일 때). 따라서 System.out.println은 n-1 번입니다.

Answer 2

이 이차 함수는 시간에 실행하는 표시 - O (N^2).

다음은 이와 같은 트릭입니다. 중첩 된 for 루프마다 n의 지수에 1을 더합니다. 3 개의 루프가있는 경우,이 알고리즘은 큐빅 시간 O (n^3)로 실행됩니다. 단 하나의 루프가 있다면 (반감이없는) 선형 O (n)이됩니다. 배열이 (재귀 적으로 또는 반복적으로) 매번 반으로된다면 대수 시간 O (log n) -> base 2로 간주됩니다.

희망이 있습니다.

Answer 3

그것을보고하는 간단한 방법이다

단일 루프 등등 O 복잡성 루프 내에 루프가 O의 복잡도를 갖는다

(N) (N^2)를 갖는다 .

그래서 위의 루프는 O의 복잡성이 규칙은, 많은 일반적인 경우에 적용 할 수 있지만, 일반적으로 사실이 아니다이며, 하나가 자신의 유효 범위에 대해 알아야 할 (N^2)