[내일배움캠프] C# 문법 종합반 - 알고리즘 (Big O)

Big O 표기법

1) Big O 표기법

Big O 표기법은 알고리즘의 효율성을 나타내는 표기법입니다.

특히, Big O 표기법은 입력의 크기에 따라 알고리즘이 얼마나 많은 시간이나 공간을 필요로 하는지를 설명합니다.

Big O 표기법은 알고리즘의 최악의 경우 성능을 나타내므로 알고리즘의 효율성을 과장하지 않습니다.

2) Big O 표기법의 예

O(1): 상수 시간. 입력의 크기에 상관없이 항상 일정한 시간이 걸립니다.O(n): 선형 시간. 입력의 크기에 비례하여 시간이 걸립니다.

O(n^2): 이차 시간. 입력의 크기의 제곱에 비례하여 시간이 걸립니다.

O(log n): 로그 시간. 입력의 크기의 로그에 비례하여 시간이 걸립니다.

BigO 표기법

3) 빅오 표기법 계산

1. 상수 버리기 알고리즘의 시간 복잡도에서 가장 큰 영향을 주는 항목을 중심으로 살펴봅니다. 상수 항목이나 낮은 차수의 항목은 빅오 표기법에서 중요하지 않으므로 버립니다. 예를 들어, O(2n), O(3n^2)와 같은 경우 O(n), O(n^2)로 간소화할 수 있습니다.
2. 최고 차수 항목만 남기기 빅오 표기법에서는 가장 빠르게 증가하는 항목에 초점을 맞춥니다. 따라서 가장 큰 차수의 항목만을 남기고 나머지는 버립니다. 예를 들어, O(n^2 + n)의 경우 O(n^2)로 간소화할 수 있습니다.
3. 다항식의 경우 최고 차수 항목만 고려 다항식의 경우 가장 빠르게 증가하는 항목에 초점을 맞춥니다. 상수항이나 낮은 차수의 항목은 무시합니다. 예를 들어, O(3n^3 + 5n^2 + 2n + 7)의 경우 O(n^3)로 간소화할 수 있습니다.
4. 연산자 상수 무시 빅오 표기법에서는 연산자나 상수 값을 무시합니다. 예를 들어, O(3n^2 + 4n + 2)의 경우 O(n^2)로 간소화할 수 있습니다.

Log개념