자료구조 빅 오

빅 오 표기법과 함수의 성장률: f(n)=0.6n^2 + ... 케이스 탐구

알고리즘의 성능 분석은 컴퓨터 과학의 중요한 주제 중 하나.

알고리즘의 실행 시간을 추정할 때, 빅 오 표기법이 널리 사용.

예를 들어, f(n)=0.6n^2 + 1000n + 3000 함수를 고려해보자.

여기서 가장 높은 차수의 항은 n^2.

따라서, 이 함수의 성장률을 대략적으로 나타내기 위해,

f(n)이 O(n^2)에 "포함된다"고 말함.

 

기호로는 f(n) ∈ O(n^2)와 같이 표현됩니다.

빅 오 표기법에서는 주로 가장 높은 차수의 항만을 고려함.

이는 그보다 낮은 차수의 항들이나 상수항은

n이 커질수록 무시할 수 있기 때문.

 

따라서 f(n)=0.6n^2 + 1000n + 3000의 성장률은

f(n) ∈ O(n^2)로 간주.

또 다른 예로 g(n) = 7n^2 함수를 생각해보자..

비록 상수 계수가 f(n)과 다르더라도,

g(n) ∈ O(n^2)의 성장률을 가진다.

 

알고리즘의 시간 복잡도: 왜 중요한가?

알고리즘의 성능을 이해하는 것은 매우 중요.

왜냐하면, 우리는 자주 큰 데이터셋이나 복잡한 연산을 다루게 되기 때문.

이러한 상황에서 효율적인 알고리즘은 시스템의 전체 성능에 큰 영향을 미침. 

빅 오 표기법은 알고리즘의 시간 복잡도를 측정하는 주요 도구 중 하나.

이 표기법은 알고리즘의 성능을 큰 O 표기법으로 표현함으로써,

알고리즘의 최악의 성능을 추정하는 데 도움을 줌.

 

예를 들어, O(n^2)의 복잡도를 가진 알고리즘은

데이터 크기가 두 배로 증가하면 실행 시간이 대략 4배 증가한다는 것을 의미.

하지만, 알고리즘의 시간 복잡도만으로 

그 성능을 완전히 평가하는 것은 한계가 있음.

 

실제 환경에서의 다양한 요소,

예를 들면 메모리 사용, 캐시 히트율, 병렬 처리 능력 등도 성능에 큰 영향을 미칠 수 있음.

그렇기에 빅 오 표기법은

알고리즘의 전체적인 성능을 파악하는 초기 단계로 사용되어야 함..

 

빅 오 표기법: O(1)의 의미와 예시

빅 오 표기법에서 O(1)은 "상수 시간" 복잡도를 나타냄.

이 표기는 알고리즘이

입력 데이터의 크기에 관계없이 항상 일정한 시간이 걸린다는 것을 의미.

예를 들어, 

크기가 1000인 배열에서 첫 번째 원소를 가져오는 작업을 생각해보자.

이 작업은 배열의 크기와 상관없이 항상 동일한 시간이 걸림.

배열에 10개의 원소가 있든, 10,000개의 원소가 있든

첫 번째 원소를 가져오는데 걸리는 시간은 동일.

이러한 연산이 O(1)의 복잡도를 가짐.

다른 예로, 

해시 테이블에서 특정 키를 가진 값을 조회하는 연산을 들 수 있음.

좋은 해시 함수와 충분한 공간이 있을 경우,

이 연산은 상수 시간에 이루어질 수 있음.

하지만 

주의할 점은, O(1)이 항상 "빠르다"는 것을 의미하는 것은 아님.

O(1)은 알고리즘의 실행 시간이 입력 크기에 따라 변하지 않는다는 것만을 의미.

실제 실행 시간은 상수 값에 따라 다를 수 있음.

O(1)의 시간 복잡도는 

많은 문제 해결 방법에서 중요한 역할을 함.

특히, 입력 데이터의 크기와 관계없이

일정한 성능을 유지해야 하는 시스템에서는

이러한 알고리즘이 큰 가치를 지님.

 

실제 알고리즘 분석에서 빅 오 표기법의 활용

빅 오 표기법을 실제 알고리즘 분석에 활용하면서 주의해야 할 몇 가지 사항들이 있음.

1. **상수는 무시함:** 
알고리즘의 성능을 대략적으로 추정할 때 상수는 큰 영향을 주지 않음. 

예를 들면, 알고리즘의 실행 시간이 n/2일 경우, 이를 O(n)으로 간주함.

2. **낮은 차수의 항은 무시함:** 
    빅 오 표기법에서는 가장 큰 영향을 주는 항만을 고려함. 

    예시로, 3n² + 15n 이라는 시간 복잡도는 O(n²)으로 간주됨.

→ 퀴즈
    함수 f(n)이 2560일 때, f(n)의 빅 오 표기법은 무엇인가?

f(n) = 2560은 상수 함수임. 

따라서, 빅 오 표기법으로는 O(1)로 표현됨. 

이것은 함수의 값이 n의 크기와 상관없이 항상 일정하다는 것을 의미함.

알고리즘 복잡도의 일반적인 범주

알고리즘의 복잡도는 그 알고리즘이 얼마나 효율적으로 동작하는지를 나타내는 지표임. 

여기서는 몇 가지 대표적인 복잡도 클래스를 소개하고 각각이 무슨 의미를 가지는지 알아보겠음.

1. **O(1) - 상수 시간 복잡도:** 
    알고리즘의 수행 시간이 입력 크기와 상관 없이 일정함. 

    예를 들어 배열의 첫 번째 원소에 접근하는 연산이 이에 해당됨.

 

 

2. **O(log n) - 로그 시간 복잡도:**      

 

이진 탐색과 같이 
입력 크기가 두 배로 늘어나도 수행 시간은 한 단위만 증가함.

아무리 큰 목록이라도 탐색해야 할 항목 수가 매번 반으로 줄어듬. 
즉, 100개의 항목이 있을 때 최대 7번 안에 원하는 항목을 찾을 수 있고,
1,000개의 항목이라면 최대 10번 안에 찾을 수 있음.
따라서 목록의 크기가 두 배로 늘어나도,
추가로 탐색해야 할 횟수는 한 번만 늘어남.

이진 탐색을 예로 들어 다시 설명하면, 책을 펼쳐 중간에 위치한 페이지를 확인하려고 한다고 상상해보자. 만약 찾고자 하는 내용이 그 페이지보다 앞에 있다면, 뒷쪽 절반의 모든 페이지는 무시할 수 있음. 다음으로 중간 페이지를 다시 찾아 그 앞, 또는 뒤를 결정하며, 이런 방식으로 원하는 페이지를 찾을 때까지 반복합니다.  즉, 1,000페이지의 책에서 원하는 내용을 찾으려면  10번 미만의 단계만으로 원하는 페이지를 찾을 수 있습니다.  10,000페이지의 책이라면? 여전히 14번 미만의 단계만으로 찾을 수 있습니다.  이처럼, 로그 시간 복잡도는 전체 데이터의 양이 늘어나더라도 필요한 단계의 수가 그리 많이 늘어나지 않는 것을 의미함.

 

3. **O(n) - 선형 시간 복잡도:**      

 

입력 크기와 수행 시간이 직선적으로 증가함. 
예를 들어, 리스트의 모든 원소를 순회하는 연산이 이에 해당됨.
알고리즘이 처리해야 할 데이터의 양에 따라 시간이 직선적으로 증가하는 경우를 말함.

예를 들면, 영화관에 줄을 서 있는 100명의 사람들에게 티켓을 나눠주는 상황. 한 사람에게 티켓을 주는 데 1분이 걸린다면, 100명의 사람들에게 티켓을 모두 나눠주기 위해서는 100분이 걸림. 만약 사람 수가 200명으로 늘어나면 200분이 걸립니다. 이처럼 처리해야 할 데이터의 양이 늘어나면 그에 비례해서 시간도 늘어나는 경우를 선형 시간 복잡도. 이러한 선형 복잡도의 대표적인 예는 배열이나 리스트의 모든 원소를 순회하는 연산.

 

4. **O(n log n) - 선형 로그 시간 복잡도:**         
    병합 정렬(merge sort)나 힙 정렬(heap sort) 같은 알고리즘에서 볼 수 있음.

 

이 시간 복잡도는 데이터의 크기가 커질수록

처리 시간이 선형적으로 증가하는 것은 아니지만,

O(n)보다는 빠르게 증가하고 O(n²)보다는 느리게 증가하는 특성을 가짐.

 

이해를 돕기 위한 예시로, 책을 정리한다고 가정~!! 각각의 책을 한 번씩 보면서 크기별로 분류하고 (이것이 O(n)), 그 다음에 각 분류된 그룹을 빠르게 정리하려면 그룹의 크기를 계속 반으로 나눠서 정리하는 방식을 사용. 이렇게 그룹을 반으로 나누는 과정이 로그의 특성을 가지며, 이를 합쳐서 O(n log n)의 시간 복잡도를 형성하게 됨. 병합 정렬(merge sort)에서는 이러한 원리로 데이터를 반으로 나누고 (이것이 log n의 특성), 각 부분을 정렬한 후 다시 병합하며 전체 리스트를 정렬. 이러한 과정에서 O(n log n)의 시간 복잡도가 발생.

5. **O(n²) - 제곱 시간 복잡도:**     
    2중 for 루프를 사용하는 버블 정렬(bubble sort) 같은 알고리즘에서 볼 수 있음.

    이 시간 복잡도는 입력 크기에 따라 처리 시간이 제곱에 비례하여 증가. 

 

간단한 예로,  친구들과 이름 순으로 앉기로 했다고 가정해보자. 당신은 매번 친구들 사이를 돌아다니며 올바른 순서를 찾아 앉히게 하는데, 이를 위해 모든 친구들을 한 번씩 확인. 그 다음 친구는 다시 모든 친구들 사이를 돌며 올바른 위치를 찾음. 이렇게 각각의 친구마다 모든 친구들을 확인하는 것이므로, 친구 수의 제곱만큼의 시간이 걸리게 됨. 이러한 특성을 가진 대표적인 알고리즘이 바로 버블 정렬(bubble sort). 버블 정렬에서는 리스트의 각 원소를 확인하면서 바로 옆의 원소와 비교하여 순서를 바꾸는 과정을 반복. 이 과정을 리스트의 길이만큼 반복하므로 O(n²)의 시간 복잡도가 발생하게 됨.

 

6. **O(2ⁿ) - 지수 시간 복잡도:** 
    풀이 시간이 입력 크기에 따라 기하급수적으로 증가함. 대부분의 경우 매우 비효율적임.

본 내용은 알고리즘의 복잡도를 평가할 때 사용되는 

빅 오 표기법의 몇 가지 일반적인 예를 간략하게 소개한 것임. 

각 복잡도 클래스는 알고리즘의 성능을 

대략적으로 추정하는 데 도움을 주는 지표로 사용됨.

 

 

 

**Big O Notation 해설**

1. **0.000001*n² + 15000*n**
   - 여기서 주목해야 할 부분은 가장 큰 차수의 항.

     상수계수는 크게 중요치 않음.
   - 결과적으로, 이 함수의 복잡도는 O(n²).

     결론 :  0.000001*n² + 15000*n ∈ O(n²)

2. **n² * n + 10n² log n**
   - n²와 n을 곱하면 n^3. 

     그리고 n²와 log n을 곱하면 n² log n.
   - 가장 큰 차수의 항이 n^3이므로, 이 함수의 복잡도는 O(n^3).

     결론 : n² * n + 10n² log n ∈ O(n^3)

3. **12345 + log 54321**

 

  12345 : 이 부분은 상수. 빅 오 표기법에서 모든 상수는 O(1) 로 표현됨.
   log 54321 : 이 부분 역시 상수.

              변수가 아닌 고정된 숫자의 로그 값을 구하는 것이므로,

              이 값은 입력의 크기나 변동성에 관계없이 항상 동일. 그러므로 O(1) 로 표현.
   결과적으로, 이 식의 복잡도는 O(1) ~!!

   왜냐하면 두 구성 요소 모두 상수 시간 복잡도를 가지기 때문.

     결론 :  12345 + log 54321  ∈ O(1)

 

 

4. **(n + log n)²**
   - 여기서는 n + log n 전체를 제곱.

     가장 큰 항은 n의 제곱.
   - 결과적으로, 이 함수의 복잡도는 O(n²).

     결론 : (n + log n)²  ∈ O (n²).

5. **n(5+log n)**
   - n과 5를 곱하면 5n이 되고, n과 log n을 곱하면 n log n.
   - 두 항 중에서 n log n이 복잡도가 더 큼.
   - 따라서, 이 함수의 복잡도는 O(n log n).

     결론 :  n(5+log n)  ∈ O( n log n).

6. **1+2+3+...+n = (n²+n)/2**
   - 가우스의 합 공식에 따르면, 1부터 n까지의 합은 (n²+n)/2.
   - 가장 큰 차수의 항은 n².
   - 결과적으로, 이 함수의 복잡도는 O(n²)입니다.

     결론 :  1+2+3+...+n = (n²+n)/2  ∈ O( n²)

이렇게 각 함수의 복잡도를 Big O 표기법으로 나타낼 수 있음.

복잡도를 계산할 때는 항상 가장 큰 차수의 항을 중심으로 생각하면 됨.

 

## 코드의 시간 복잡도 분석 ```python for i in range(n):     # do something

위 코드는 n번의 반복문을 수행.

따라서 주어진 코드의 시간 복잡도는 O(n) 

이는 n이 증가함에 따라 반복문 내부에서 수행되는

연산의 횟수도 선형적으로 증가하기 때문.

 

## 코드의 시간 복잡도 분석 ```python for i in range(n):     for j in range(n):         # do something

위 코드는 외부 반복문이 n번 실행되며, 

각 외부 반복문의 실행마다 내부 반복문도 n번 실행됨.

이렇게 중첩된 두 개의 반복문은 n x n = n²번의 연산을 수행.

따라서 주어진 코드의 시간 복잡도는 O(n²).

 

## 삽입 정렬 (Insertion Sort)

삽입 정렬은 많은 애플리케이션에서 필요한 정렬 알고리즘.

이 방법의 기본 아이디어는 다음과 같음:
- 부분적으로 정렬된 배열에 다음 원소를 삽입.
- 이 과정을 반복.

원소를 삽입할 때 기존의 원소들을 옮기는 것이 필요.

### 예제

- **입력**: n개의 숫자들의 순서 (a₁, a₂, ..., an)
- **출력**: 입력된 순서의 순열로, a₁ ≤ a₂ ≤ ... ≤ an 이런 식으로 재배열된다.

5 2 4 6 1 3

(1라운드) 2 5 | 4 6 1 3

(2라운드) 2 4 5 | 6 1 3

(3라운드) 2 4 5 6 | 1 3

(4라운드) 1 2 4 5 6 | 3

(5라운드) 1 2 3 4 5 6 |

 

위의 예시를 보면, 각 단계에서 적절한 위치에 숫자를 삽입하여

전체 리스트를 점차적으로 정렬하는 과정을 볼 수 있음.

## 선택정렬

가장 작은 수를 기억하여 확정되면 위치를 바꾼다.

기호 전) 나름 정렬 완료 | 기호 후) 정렬전

(a) 5 2 4 6 1 3

1라운드 : 1 |  2 4 6 5 3  

   :: 최소인 1을 찾았으니 5와 자리 교체

2라운드 : 1  2  |  4 6 5 3  

3라운드 : 1  2  3 |  6 5 4  ::최소인 3을 4와 교체

4라운드 : 1  2  3  4  |  5 6  ::최소인 4을 6와 교체

5라운드 : 1  2  3  4  5 |  6

6라운드 : 1  2  3  4  5  6 |