Big O 표기법

11.1 Big O 표기법 정의

Big O 표기법은 수학적 표기법으로, 입력 데이터의 크기에 따라 알고리즘의 실행 시간이나 자원 소비의 상한을 설명하는 데 사용돼. 이거는 알고리즘이 얼마나 잘 확장되고, 데이터의 양이 증가할 때 성능이 어떻게 변하는지 파악하는 데 도움이 돼.

Big O 표기법은 알고리즘의 가장 중요한 측면에 집중하고, 상수와 덜 중요한 항은 무시하여 알고리즘의 장기적인 동작에 집중할 수 있게 해줘.

주요 표기법:

O(1) — 상수 복잡도:

• 알고리즘의 실행 시간이 입력 데이터의 크기에 의존하지 않아.
• 예: 배열에서 인덱스로 값 접근.

O(n) — 선형 복잡도:

• 알고리즘의 실행 시간이 입력 데이터의 크기에 선형적으로 의존해.
• 예: 배열의 모든 요소를 간단히 순회하는 것.

O(log n) — 로그 복잡도:

• 알고리즘의 실행 시간이 입력 데이터의 크기 증가에 따라 로그로 증가해.
• 예: 정렬된 배열에서 이진 검색.

O(n^2) — 제곱 복잡도:

• 알고리즘의 실행 시간이 입력 데이터의 크기에 제곱으로 의존해.
• 예: 버블 정렬, 삽입 정렬.

O(2^n) — 지수 복잡도:

• 알고리즘의 실행 시간이 입력 데이터의 크기에 지수적으로 의존해.
• 예: 배낭 문제를 전체 탐색으로 해결.

참고. 이진 검색, 버블 정렬, "배낭 문제"에 대해 자세한 내용은 다음 강의에서 다룰 거야.

11.2 Big O 표기법 해석

Big O 표기법을 어떻게 해석하고 사용할까?

상수와 덜 중요한 항 무시하기: Big O는 함수의 성장 순서를 설명하며 상수와 덜 중요한 항을 무시해. 예를 들어, O(2n)와 O(3n)은 O(n)으로 해석돼.

알고리즘 비교하기: Big O는 알고리즘을 비대칭 효율성으로 비교할 수 있게 해줘. 예를 들어, O(n log n)인 알고리즘은 많은 데이터 양에서 O(n^2)인 알고리즘보다 더 효율적이야.

최악의 경우 분석: Big O는 주로 알고리즘의 최악의 경우 실행 시간을 분석하는 데 사용되며, 최대 복잡도를 평가할 수 있게 해줘.

상수 무시

상수와 덜 중요한 항을 무시하는 예를 살펴보자:

예제 1. 두 함수를 고려해 보자:

• f(n) = 3n + 2
• g(n) = 5n + 1

두 함수는 선형 복잡도를 가지고 있어, 각 함수에서 지배적인 항이 n이기 때문에. 따라서 두 함수는 각기 다른 계수와 추가 항에도 불구하고 O(n)으로 해석돼.

예제 2. 두 함수를 고려해 보자:

• f(n) = n^2 + 3n + 4
• g(n) = 2n^2 + n

두 함수는 제곱 복잡도를 가지고 있어, 지배적인 항이 n^2이기 때문에. 두 표현식은 각기 다른 계수와 나머지 항에도 불구하고 O(n^2)으로 해석돼.

11.3. 알고리즘 비교

1. 매우 큰 데이터 양에서 알고리즘 비교

예제 1:

• 알고리즘 A는 O(n^2) 시간 복잡도를 가짐.
• 알고리즘 B는 O(n log n) 시간 복잡도를 가짐.

작은 n에서 A 알고리즘은 작은 상수 때문에 더 빨리 작동할 수 있지만, 큰 n에서는 B 알고리즘이 훨씬 더 빠를 거야, 왜냐면 성장이 로그로 이루어지니까, 제곱이 아니라.

예제 2:

• 알고리즘 X는 O(n) 시간 복잡도를 가짐.
• 알고리즘 Y는 O(1) 시간 복잡도를 가짐.

Y 알고리즘은 항상 더 빨리 작동할 거야, 입력 데이터의 크기에 상관없이, 왜냐면 O(1)은 알고리즘 실행 시간이 입력 데이터의 크기에 의존하지 않음을 의미하기 때문이야.

2. 최악의 경우 분석

예제 1:

버블 정렬 알고리즘은 최악의 경우 O(n^2) 시간 복잡도를 가지고 있는데, 배열이 역순으로 정렬된 경우야. 이건 배열의 각 요소에 대해 다른 모든 요소와 비교 및, 아마도 교환을 필요로 함을 뜻해.

예제 2:

이진 검색은 최악의 경우 O(log n) 시간 복잡도를 가지고 있어. 이건 최악의 경우에도 요소를 찾는데 필요한 단계 수가 배열 크기에 로그로 의존함을 뜻해, 매우 효율적이지.

3. 성능 및 확장성에 대한 영향

예제 1:

데이터를 처리하는 두 가지 알고리즘이 있다면, 하나는 O(n^2) 그리고 다른 하나는 O(n log n) 시간 복잡도를 가진, 그리고 우리가 데이터 크기를 1000개의 요소에서 10,000개의 요소로 증가시킬 때, 성능 차이는 상당히 눈에 띄게 될 거야.

• O(n^2) 복잡도를 가진 알고리즘은 10,000개의 요소에 대해 약 100,000,000번의 연산을 수행할 거야.
• O(n log n) 복잡도를 가진 알고리즘은 10,000개의 요소에 대해 약 40,000번의 연산을 수행할 거야.

예제 2:

O(2^n)으로 작동하는 알고리즘을 고려해봐. 우리는 입력 데이터 크기를 10에서 20개로 증가시키면, 연산 수가 지수적으로 증가해.

• n = 10: 2^10 = 1024 연산.
• n = 20: 2^20 = 1,048,576 연산.

이것은 큰 n 값에 대해 지수 복잡도가 얼마나 빠르게 비실용적으로 변하는지를 보여줘.

1

Опрос

데이터 구조,  52 уровень,  4 лекция

недоступен

데이터 구조

데이터 구조

Открыть