1. 개요

이 예제에서는 Big O Notation이 의미하는 바에 대해 설명 합니다. 코드 실행 시간에 미치는 영향을 조사하기 위해 몇 가지 예를 살펴 보겠습니다.

2. Big O 표기법의 직관

우리는 종종 Big O Notation을 사용하여 설명 된 알고리즘 의 성능을 듣습니다 .

알고리즘의 성능 또는 알고리즘 복잡성에 대한 연구는 알고리즘 분석 분야에 속합니다 . 알고리즘 분석은 알고리즘이 사용하는 디스크 공간 또는 시간과 같은 리소스의 수에 대한 질문에 답합니다.

우리는 시간을 자원으로 볼 것입니다. 일반적으로 알고리즘을 완료하는 데 걸리는 시간이 짧을수록 좋습니다.

3. 일정 시간 알고리즘 – O (1)

알고리즘의이 입력 크기는 실행 시간에 어떤 영향을 미칩니 까? Big O를 이해하는 열쇠는 사물이 성장할 수있는 속도를 이해하는 것입니다. 여기서 문제의 비율은 입력 크기 당 소요되는 시간입니다.

이 간단한 코드를 고려하십시오.

int n = 1000;
System.out.println("Hey - your input is: " + n);

분명히, 위의 n 이 무엇인지 는 중요하지 않습니다 . 이 코드 조각은 실행하는 데 일정한 시간이 걸립니다. n의 크기에 의존하지 않습니다.

비슷하게:

int n = 1000;
System.out.println("Hey - your input is: " + n);
System.out.println("Hmm.. I'm doing more stuff with: " + n);
System.out.println("And more: " + n);

위의 예도 일정 시간입니다. 실행하는 데 3 배가 걸리더라도  입력 크기 n에 의존하지 않습니다.  상수 시간 알고리즘을 다음과 같이 표시합니다. O (1) . 참고 O (2) , O (3) 또는 O (1000) 같은 것을 의미 할 것입니다.

우리는 정확히 얼마나 오래 걸리는지 신경 쓰지 않고 단지 일정한 시간이 걸린다는 것입니다.

4. 로그 시간 알고리즘 – O (log n)

일정 시간 알고리즘이 (점근 적으로) 가장 빠릅니다. 로그 시간이 그 다음으로 빠릅니다. 불행히도 그들은 상상하기가 조금 더 까다 롭습니다.

로그 시간 알고리즘의 한 가지 일반적인 예는 이진 검색 알고리즘입니다. Java에서 바이너리 검색을 구현하는 방법을 보려면 여기를 클릭하십시오.

여기서 중요한 것은 입력의 로그에 비례 하여 실행 시간이 증가 한다는 것입니다 (이 경우 밑이 2에 로그).

for (int i = 1; i < n; i = i * 2){
    System.out.println("Hey - I'm busy looking at: " + i);
}

경우 n은 8이며, 출력이 다음에 해당합니다

Hey - I'm busy looking at: 1
Hey - I'm busy looking at: 2
Hey - I'm busy looking at: 4

우리의 간단한 알고리즘은 log (8) = 3 번을 실행했습니다.

5. 선형 시간 알고리즘 – O (n)

로그 시간 알고리즘 이후, 다음으로 빠른 클래스 인 선형 시간 알고리즘을 얻습니다 .

어떤 것이 선형 적으로 성장한다고 말하면 입력 크기에 정비례하여 성장한다는 의미입니다.

간단한 for 루프를 생각해보십시오.

for (int i = 0; i < n; i++) {
    System.out.println("Hey - I'm busy looking at: " + i);
}

이 for 루프는 몇 번 실행됩니까? 물론 n 번! 이 작업이 실행되는 데 얼마나 오래 걸릴지 정확히 알 수 없으며 그것에 대해 걱정하지 않습니다.

우리가 아는 것은 위에 제시된 간단한 알고리즘이 입력 크기에 따라 선형 적으로 증가한다는 것입니다.

(1000n + 1000) 보다 0.1n 의 실행 시간을 선호 하지만 둘 다 여전히 선형 알고리즘입니다. 둘 다 입력의 크기에 비례하여 직접 성장합니다.

다시, 알고리즘이 다음과 같이 변경된 경우 :

for (int i = 0; i < n; i++) {
    System.out.println("Hey - I'm busy looking at: " + i);
    System.out.println("Hmm.. Let's have another look at: " + i);
    System.out.println("And another: " + i);
}

런타임은 입력 n 크기에서 여전히 선형입니다 . 선형 알고리즘을 다음과 같이 표시합니다. O (n) .

상수 시간 알고리즘과 마찬가지로 런타임의 세부 사항에 대해서는 신경 쓰지 않습니다. O (2n + 1) 은 O (n) 과 동일합니다. Big O 표기법은 입력 크기의 증가와 관련이 있기 때문입니다.

6. N Log N 시간 알고리즘 – O (n log n)

n log n 은 다음 클래스의 알고리즘입니다.  실행 시간은입력의 n log n 에 비례하여 증가합니다.

for (int i = 1; i <= n; i++){
    for(int j = 1; j < n; j = j * 2) {
        System.out.println("Hey - I'm busy looking at: " + i + " and " + j);
    }
}

예를 들어  n 이 8이면이 알고리즘은 8 * log (8) = 8 * 3 = 24 번 실행됩니다. for 루프에서 우리가 엄격한 부등식을 가지고 있는지 여부는 Big O 표기법과 관련이 없습니다.

7. 다항식 시간 알고리즘 – O (n p )

다음으로 다항식 시간 알고리즘이 있습니다. 이러한 알고리즘은 n log n 알고리즘 보다 훨씬 느립니다 .

다항식이라는 용어는 2 차 (n 2 ) , 3 차  (n 3 ) , 4 차 (n 4 ) 등의 함수 를 포함하는 일반 용어입니다 . 중요한 것은 O (n 2 ) 가  O (n 4 ) 보다 빠른 O (n 3 ) 보다 빠르다는 것입니다  .

2 차 시간 알고리즘의 간단한 예를 살펴 보겠습니다.

for (int i = 1; i <= n; i++) {
    for(int j = 1; j <= n; j++) {
        System.out.println("Hey - I'm busy looking at: " + i + " and " + j);
    }
}

이 알고리즘은 8 2  = 64 회 실행됩니다  . 또 다른 for 루프를 중첩하면  O (n 3 ) 알고리즘이됩니다.

8. 지수 시간 알고리즘 – O ( k n )

이제 우리는 위험한 영역으로 들어가고 있습니다. 이러한 알고리즘은 입력 크기에 의해 지수화 된 일부 요인에 비례하여 증가합니다.

예를 들어, O (2 n ) 알고리즘은 추가 입력마다 두 배가됩니다. 따라서 n = 2 이면 이러한 알고리즘은 4 번 실행됩니다. 만약 N = 3 , 그들은 (일종의 시간 대수 알고리즘의 양 등) 8 번 실행된다.

O ( 3n ) 알고리즘은 모든 추가 입력에 대해 세 배가되고  O (k n ) 알고리즘은 추가 입력마다 k 배 더 커집니다.

O (2 n ) 시간 알고리즘 의 간단한 예를 살펴 보겠습니다  .

for (int i = 1; i <= Math.pow(2, n); i++){
    System.out.println("Hey - I'm busy looking at: " + i);
}

이 알고리즘은 2 8  = 256 회 실행됩니다  .

9. 팩토리얼 시간 알고리즘 – O (n!)

대부분의 경우 이것은 얻을 수있는 것만 큼 나쁘다. 이 알고리즘 클래스  에는 입력 크기 의 계승 에 비례하는 런타임이 있습니다.

이에 대한 전형적인 예  는 무차별 대입 접근 방식을 사용하여 출장 세일즈맨 문제를 해결하는 것입니다.

출장 판매원 문제에 대한 해결책에 대한 설명은이 기사의 범위를 벗어납니다.

대신 이전 섹션에서와 같이 간단한 O (n!) 알고리즘을 살펴 보겠습니다 .

for (int i = 1; i <= factorial(n); i++){
    System.out.println("Hey - I'm busy looking at: " + i);
}

여기서  계승 (N)은 단지 N 계산! n이 8이면이 알고리즘은 8 을 실행합니다 ! = 40320 배.

10. 점근 함수

Big O는 점근 함수 로 알려진 것입니다  . 이 모든 것은 한계에서 알고리즘의 성능, 즉 많은 입력이 던져 질 때 자체적으로 관련된다는 것을 의미  합니다.

Big O는 알고리즘이 작은 크기의 입력으로 얼마나 잘 작동하는지 신경 쓰지 않습니다. 큰 입력과 관련이 있습니다 (100 만 개의 숫자 List 정렬과 5 개 숫자 List 정렬).

주목해야 할 또 다른 점 은 다른 점근 함수 가 있다는 것입니다. Big Θ (theta)와 Big Ω (omega)는 둘 다 한계에서 알고리즘을 설명합니다 (이 한계 는 거대한 입력에 대해 의미 하는 한계 임을 기억하십시오  ).

이 세 가지 중요한 함수의 차이점을 이해하려면 먼저 Big O, Big Θ 및 Big Ω 각각이 집합 (즉, 요소 ​​모음)을 설명한다는 것을 알아야합니다  .

여기에서 우리 세트의 구성원은 알고리즘 자체입니다.

  • Big O 는 특정 속도보다 나쁘지 않게 실행되는 모든 알고리즘 세트를 설명합니다 (상한값).
  • 반대로 Big Ω 은 특정 속도 (하한)보다 더 잘 실행 되지 않는 모든 알고리즘 집합을 나타  냅니다.
  • 마지막으로 Big Θ 는 특정 속도로 실행 되는 모든 알고리즘 집합을 설명합니다  (동등성과 유사).

위에서 설명한 정의는 수학적으로 정확하지는 않지만 이해에 도움이됩니다.

일반적으로 Big O를 사용하여 설명하는 내용을들을 수 있지만 Big Θ 및 Big Ω에 대해 아는 것은 나쁘지 않습니다.

11. 결론

이 기사에서는 Big O 표기법과 알고리즘의 복잡성을 이해하는 것이 코드의 실행 시간에 어떤 영향을 미칠 수 있는지에 대해 논의했습니다 .

다양한 복잡성 클래스에 대한 훌륭한 시각화는 여기에서 찾을 수 있습니다.

평소처럼이 예제의 코드 스 니펫은 GitHub 에서 찾을 수 있습니다 .