[알고리즘] 시간복잡도, 빅오(Big-O) 표기법 이해하기 및 자주 쓰이는 함수의 시간복잡도

빅오(Big O)는 알고리즘의 성능을 표기하는 표기법 중 하나로, 알고리즘의 시간 복잡도를 나타내는데 사용됩니다. 시간 복잡도는 알고리즘이 입력 크기에 따라 얼마나 많은 연산을 수행하는지를 나타냅니다. 빅오 표기법은 알고리즘의 성능을 "최악의 경우"에 대해 나타내므로, 알고리즘이 최악의 상황에서 얼마나 효율적으로 동작하는지를 알려줍니다.

 

빅오 표기법은 "O(f(n))"과 같은 형식으로 표기됩니다. 여기서 f(n)은 입력 크기 n에 대한 함수입니다. 빅오 표기법에서 함수 f(n)은 상수 계수, 낮은 차수의 항, 상수 값을 무시하고 가장 큰 영향을 주는 항만을 고려합니다.

다음은 일반적으로 사용되는 몇 가지 빅오 표기법의 예입니다:

 

1. O(1): 상수 시간 복잡도. 입력 크기에 관계없이 일정한 시간 내에 실행됩니다. 예를 들어, 배열에서 특정 위치에 있는 요소를 가져오는 것은 상수 시간이 소요됩니다.
2. O(log n): 로그 시간 복잡도. 입력 크기에 비례하지 않고, 입력 크기의 로그에 비례하여 실행됩니다. 예를 들어, 정렬된 배열에서 이진 검색을 수행하는 것은 로그 시간이 소요됩니다.
3. O(n): 선형 시간 복잡도. 입력 크기에 정비례하여 실행됩니다. 예를 들어, 배열의 모든 요소를 순회하는 것은 배열의 크기에 비례하여 시간이 소요됩니다.
4. O(n^2): 이차 시간 복잡도. 입력 크기의 제곱에 비례하여 실행됩니다. 예를 들어, 이중 반복문을 사용하여 모든 배열 요소 쌍을 비교하는 것은 이차 시간이 소요됩니다.
5. O(2^n): 지수 시간 복잡도. 입력 크기에 대해 지수적으로 증가하여 실행됩니다. 예를 들어, 모든 부분 집합을 생성하는 것은 입력 크기에 따라 2의 거듭제곱으로 시간이 소요됩니다.

이외에도 O(n log n), O(n!) 등 다양한 빅오 표기법이 있으며, 알고리즘의 성능을 분석하고 예측하는 데 도움을 줍니다. 이러한 표기법은 알고리즘의 효율성을 비교하고 최적화하는 데 유용하며, 알고리즘의 설계와 분석에 중요한 개념입니다.

 

파이썬에서 자주 사용되는 몇 가지 함수들의 시간 복잡도를 전부 알려드리겠습니다:

• len(): O(1)입니다. 
• append(): O(1)입니다. 리스트의 길이가 늘어나도 상수 시간에 요소를 추가할 수 있습니다.
• pop(): O(1)입니다. 마지막 요소를 제거하는 경우에는 상수 시간이 소요되지만, 특정 인덱스의 요소를 제거하는 경우에는 해당 인덱스 이후의 모든 요소를 이동시켜야 하므로 O(n)의 시간 복잡도를 가질 수도 있습니다.
• sort(): 리스트를 정렬하는 함수입니다. 정렬 알고리즘에 따라 시간 복잡도가 다르지만, 일반적인 파이썬의 sort() 함수는 O(n log n)의 시간 복잡도를 가집니다. 따라서 리스트의 크기에 따라 약간 더 느린 선형 로그 시간이 소요됩니다.
• min(), max(): O(n)입니다. 리스트의 모든 요소를 비교해야 하기 때문에 입력 크기에 비례하여 선형적으로 실행됩니다.
• index(): O(n)입니다. 리스트를 처음부터 끝까지 순회하면서 값을 비교해야 하기 때문에 입력 크기에 비례하여 선형적으로 실행됩니다.
• count(): O(n)입니다. 리스트를 처음부터 끝까지 순회하면서 값을 비교하고 개수를 세야 하므로 입력 크기에 비례하여 선형적으로 실행됩니다.
• insert(): O(n)입니다. 특정 인덱스 이후의 모든 요소를 이동시켜야 하기 때문에 입력 크기에 비례하여 선형적으로 실행됩니다.
• remove(): O(n)입니다. 리스트를 처음부터 끝까지 순회하면서 값을 비교하고 제거해야 하므로 입력 크기에 비례하여 선형적으로 실행됩니다.
• extend(): 리스트에 다른 리스트나 이터러블의 모든 요소를 추가하는 함수입니다. extend() 함수의 시간 복잡도는 입력되는 이터러블의 길이에 비례합니다. 따라서 입력의 크기에 따라 선형적으로 실행됩니다.
• reverse(): O(n)입니다. 리스트의 모든 요소를 순회하며 순서를 뒤집어야 하므로 입력 크기에 비례하여 선형적으로 실행됩니다.

알고리즘의 시간 복잡도는 구현 방식에 따라 다를 수 있으므로 위에서 설명한 시간 복잡도는 일반적인 경우를 기준으로 한 것입니다.