알고리즘 복잡도 표현 방법

1. 알고리즘 복잡도 계산이 필요한 이유

알고리즘을 설계하고 구현할 때는 이러한 복잡도를 최소화하려고 노력해야 한다. 그 이유는 시간 복잡도가 높은 알고리즘은 실행 시간이 길어져 사용자에게 대기 시간을 늘리며, 공간 복잡도가 높은 알고리즘은 많은 메모리를 사용하여 시스템의 다른 부분이 필요로 하는 메모리를 줄인다. 따라서, 알고리즘의 복잡도는 그 알고리즘의 효율성과 성능에 직접적인 영향을 미치며, 좋은 알고리즘은 동시에 시간 복잡도와 공간 복잡도를 최소화하려고 노력한다.

예를들어, 정수의 절댓값을 구할 때, 문제를 푸는 알고리즘이 다양할 수 있다.

• 방법1: 정수값을 제곱한 값에 다시 루트를 씌우기
• 방법2: 정수가 음수인지 확인해서, 음수일 때만, -1을 곱하기

다양한 알고리즘 중 어느 알고리즘이 더 좋은지를 분석하기 위해, 복잡도를 정의하고 계산한다.

2. 알고리즘 복잡도 계산 항목

알고리즘 복잡도는 알고리즘이 얼마나 효율적인지를 측정하는 방법이다. 복잡도는 일반적으로 두 가지 주요 유형으로 나뉜다. 시간 복잡도와 공간 복잡도다.

1. 시간 복잡도: 이는 알고리즘이 문제를 해결하는 데 얼마나 많은 시간이 필요한지를 측정한다. 시간 복잡도는 일반적으로 입력 데이터의 크기에 따라 얼마나 많은 단계가 필요한지를 나타낸다. 대표적으로 '빅 오' 표기법(O 표기법)을 사용하여 표현한다. 예를 들어, O(N)은 입력 크기에 선형적으로 비례하는 시간이 걸린다는 것을 의미하고, O(N^2)은 입력 크기의 제곱에 비례하는 시간이 걸린다는 것을 의미한다.

2. 공간 복잡도: 이는 알고리즘이 문제를 해결하는 데 얼마나 많은 메모리 공간이 필요한지를 측정한다. 공간 복잡도는 일반적으로 알고리즘이 실행되는 동안 필요한 메모리 양을 나타낸다.

시간 복잡도가 매우 중요하므로, 꼭 이해하고 계산할 수 있어야 한다.

알고리즘 시간 복잡도의 요소

알고리즘의 시간 복잡도는 알고리즘이 실행되는 동안 수행하는 주요 연산의 수에 크게 의존한다. 이는 일반적으로 다음과 같은 요소들에 의해 결정된다.

1. 알고리즘의 자료구조: 사용되는 자료구조는 알고리즘의 시간 복잡도에 큰 영향을 미친다. 예를 들어, 배열과 연결 리스트는 모두 선형 데이터 구조이지만, 특정 요소에 액세스하거나 요소를 삽입하거나 삭제하는 데 필요한 시간은 크게 다르다.
2. 입력 데이터의 크기: 데이터의 크기가 클수록 처리에 더 많은 시간이 필요하므로, 시간 복잡도는 일반적으로 입력 데이터의 크기에 비례한다.
3. 알고리즘의 로직: 특정 알고리즘이 문제를 해결하는 방식도 시간 복잡도에 영향을 미친다. 예를 들어, 정렬 알고리즘의 경우, 버블 정렬은 O(n^2)의 시간 복잡도를 가지는 반면, 병합 정렬은 O(n log n)의 시간 복잡도를 가진다.
4. 반복문과 재귀 호출: 반복문이나 재귀 호출은 알고리즘 내에서 수행되는 연산의 수를 크게 증가시킨다. 이러한 구조가 많이 사용될수록 알고리즘의 시간 복잡도는 높아질 가능성이 크다.

이 외에도 다양한 요소들이 알고리즘의 시간 복잡도에 영향을 미칠 수 있다. 따라서 알고리즘을 설계하거나 선택할 때는 해당 알고리즘의 시간 복잡도를 고려하는 것이 중요하다.

알고리즘 성능 표기법

1. Big O 표기법 (O-notation): Big O 표기법은 알고리즘의 최악의 성능을 나타낸다. 알고리즘에 가장 큰 입력 크기를 제공했을 때 알고리즘이 얼마나 많은 작업을 수행할지를 설명한다. 예를 들어, O(n)은 알고리즘이 최악의 경우에 선형 시간을 걸린다는 것을 의미하며, O(n^2)는 알고리즘이 최악의 경우에 제곱 시간을 걸린다는 것을 의미한다.

2. Omega 표기법 (Ω-notation): Omega 표기법은 알고리즘의 최선의 성능을 나타낸다. 즉, 알고리즘이 가장 적은 작업을 수행할 때의 성능을 설명한다. 예를 들어, Ω(n)은 알고리즘이 최선의 경우에 선형 시간을 걸린다는 것을 의미한다.

3. Theta 표기법 (θ-notation): Theta 표기법은 알고리즘의 평균 성능을 나타낸다. 알고리즘이 평균적으로 얼마나 많은 작업을 수행할지를 설명한다. Theta 표기법은 일반적으로 Big O 표기법과 Omega 표기법 사이의 상호 작용을 설명하기 위해 사용된다.

빅오 표기법

입력 n애 따라 결정되는 시간 복잡도 함수

빅 오 표기법(Big O notation)은 알고리즘의 시간 복잡도와 공간 복잡도를 나타내는데 사용되는 수학적 표기법이다. 이 표기법은 입력 데이터의 크기에 따라 알고리즘의 실행 시간이나 메모리 사용량이 어떻게 변화하는지를 간략하게 설명하는 방법을 제공한다. 빅 오 표기법은 알고리즘의 "최악의 경우" 성능을 나타낸다.

다음은 몇 가지 주요 빅 오 표기법의 예이다.

• O(1): 알고리즘이 일정한 시간 내에 실행됨을 의미한다. 입력 데이터의 크기와 무관하게 알고리즘은 항상 같은 시간을 소요한다.
• O(N): 알고리즘의 실행 시간이 입력 데이터의 크기에 선형적으로 비례함을 의미한다. 입력 데이터가 두 배로 늘어나면, 알고리즘의 실행 시간도 대략 두 배로 늘어난다.
• O(N^2): 알고리즘의 실행 시간이 입력 데이터의 제곱에 비례함을 의미한다. 버블 정렬이나 삽입 정렬 같은 알고리즘이 이 범주에 속한다.
• O(log N): 알고리즘의 실행 시간이 입력 데이터의 로그에 비례함을 의미한다. 이진 검색이 이 범주에 속한다.
• O(N log N): 알고리즘의 실행 시간이 N에 로그 N을 곱한 값에 비례함을 의미한다. 퀵 정렬이나 병합 정렬과 같은 알고리즘이 이 범주에 속한다.

이 외에도 여러 가지 빅 오 표기법이 있으며, 각각 알고리즘의 실행 시간이 어떻게 증가하는지를 설명한다. 이를 통해 우리는 알고리즘의 효율성을 비교하고, 입력 데이터의 크기가 커짐에 따라 어떤 알고리즘이 더 효율적인지 판단할 수 있다.

예제1 (1부터 n까지의 합을 구하는 알고리즘1)

def sum_all(n):
	total = 0
    for num in range(1, n+1):
    	total += num
    return total
sum_all(100) # 5050

n의 개수에 따라서, 반복문이 n번 수행되므로, 시간 복잡도는 O(n)이다.

예제2 (1부터 n까지의 합을 구하는 알고리즘2)

def sum_all(n)
	return int(n*(n+1)/2)

반복문이 없으므로, 시간 복잡도는 1이므로, 빅오 표기법으로 O(1)이다.