[CS] 빅 오 표현법(Big O Notation) 시간 복잡도

개인 공부를 하며 정리한 글입니다.

틀린 부분, 수정할 부분이 있다면 언제든 피드백 환영입니다 :)

 

알고리즘, 자료구조를 공부하면서 항상 드는 생각은 얘내들을 어느 상황에서 사용할까였다.

그 기준의 하나가 되는 것이 오늘 다룰 빅 오 표현법이다. 

 

알고리즘, 자료구조 챕터에서 항상 나오는 빅 오 표현법에 대해 간단히 알아보자.

• 알고리즘의 성능이나 복잡도를 설명하는 데 일반적으로 사용되는 방법이 빅 오 (Big O) 표현법이다.
• 알고리즘의 스피드 표현법이다.  (하지만 실제 러닝타임을 표시하는 것은 아니다.)
• 각 알고리즘의 장단점과 언제 무엇을 쓸지 빠르게 파악이 가능하다.

 

대충 빠르다, 느리다 라고 표현할 순 없잖은가...? 이걸 알면 시간복잡도를 보다 쉽게 설명할 수 있다.

( n은 가로축의 입력 사이즈를 말한다. 여기선 이해하기 쉽게  한번의 연산 사이클이라고 하겠다. )

 

그럼 코드로 이해 해보자.

---

1.  constant time  ( 상수 시간 ):  O(1)

 

입력 데이터 크기에 상관없이 언제나 일정한 시간이 걸리는 알고리즘을 말한다.

function exampleConstantFunc(n) {
    return n*n;
}

 

예를 들어 인덱스로 배열의 요소에 액세스하고 해시 테이블에 요소를 삽입/삭제하는 경우 

 

 

 

2. Linear time ( 선형 시간 ) : O(n) 

 

O(n)은 선형 시간으로 최악의 시나리오에서 n개의 연산을 수행해야 하는 알고리즘에 적용됩니다.

대부분은 단순한 기본 루프이며 그 안에서 일정한 시간 연산을 수행합니다.

런타임은 입력 크기에 정비례하여 증가합니다. 

function exampleLinear(n) {
    for (var i = 0 ; i < n; i++ ) {
        console.log(i)
    }
}

 

예를 들어 정렬되지 않은 배열에서 최대 또는 최소 요소를 찾는 경우 

 

3. Logarithmic time ( 로그 시간 ) : O(log(n))

 

로그 시간 함수는 실행 시간이 입력 크기의 로그에 비례하는 함수입니다. 

입력이 증가함에 따라 런타임이 천천히 증가합니다. 

 

function log(n) {
    for (let i = 1; i < n; i*=2) {
        const result = i;
        console.log(result);  
    }
}

 

주어진 반복에서 i의 값은 2i이므로 n번째 반복에서 i의 값은 2n이라는 것을 알 수 있습니다. 

또한 i의 값은 항상 루프 자체의 크기(N)보다 작다는 것을 알고 있습니다. 

이를 통해 다음과 같은 결과를 추론할 수 있습니다: 2^n < N log(2^n) < log(N) n < log(N) 앞의 코드에서 반복 횟수는 항상 입력 크기의 로그보다 작다는 것을 알 수 있습니다. 

따라서 이러한 알고리즘의 최악의 시간 복잡성은 O(log(n))입니다. 

로그 시간 복잡성의 효율성은 백만 개의 항목과 같은 큰 입력에서 분명하게 나타납니다.

 

예를 들어 정렬된 배열에 대한 이진 검색과 균형 이진 검색 트리에 대한 연산은 이에 해당 됩니다.

 

4. Quadratic time( 이차 시간 ) : O(n^2 )

이차 시간 알고리즘을 사용하면 이제 시간 복잡성의 낮은 효율을 볼 수 있습니다.

이름에서 알 수 있듯이 입력의 크기는 알고리즘의 실행 시간에 제곱으로 영향을 미치며

런타임은 입력 크기에 따라 기하급수적으로 증가합니다.

 

일반적인 예로 중첩 루프를 들 수 있습니다:

for (int i = 0; i <n; i += c) {
    for (int j = 0; j < n; j += c) {
    ...
    }
}

 

앞의 예에서 볼 수 있듯이, i = 0의 경우 내부 루프는 n번 실행되고, i = 1, i = 2 등에서도 동일하게 실행됩니다. 내부 루프는 항상 n번 실행되며 n의 값에 의존하지 않으므로 알고리즘의 시간 복잡도는 O(n2)가 됩니다.

 

예를 들어 버블 정렬, 삽입 정렬, 선택 정렬과 같은 간단한 정렬 알고리즘의 경우가 이에 해당 됩니다.

 

 

 

5. Polynomial time( 다항식 시간 ): O(n^n)

다항식 시간 복잡도는 알고리즘의 실행 시간 복잡도로, nk의 순서로 실행됩니다.

이차 시간 알고리즘은 k = 2인 특정 유형의 다항식 시간 알고리즘입니다.

이러한 알고리즘의 아주 간단한 예는 다음과 같습니다:

for (int i = 0; i <n; i += c) {
    for (int j = 0; j < n; j += c) {
        for (int k = 0; k < n; k += c) {
            // some O(1) expressions
        }
    }
}

 

 

보시다시피 이 예제는 이차 시간 섹션의 예제를 확장한 것일 뿐입니다. 이 경우의 최악의 복잡도는 O(n3)입니다. 보시다시피 이 예제는 이차 시간 섹션의 예제를 확장한 것일 뿐입니다. 이 경우의 최악의 복잡도는 O(n3)입니다.

 

 

아래의 링크를 통해 좀 더 많은 정보를 얻을 수 있습니다.

 

https://daunje0.tistory.com/171

[CS] 알고리즘의 공간 복잡도(Space Complexity)란?

 

 

 

https://www.youtube.com/post/UgkxjckMRttgxDN36hILcIq3eN5FVNHzDxcb

ByteByteGo님의 게시물

 

 

https://www.devopsschool.com/blog/complete-tutorial-on-big-o-big-oh-notation/

 

Complete Tutorial on big O (big oh) notation - DevOpsSchool.com

 

 

https://dev.to/b0nbon1/understanding-big-o-notation-with-javascript-25mc

Understanding Big-O Notation With JavaScript