Introduction to Algorithms(알고리즘 소개)
- 알고리즘이란 무엇인가?
문제를 해결하는 단계적 절차!
결국은 느린 컴퓨터에서 실행되는 더 빠른 알고리즘이 빠른 컴퓨터에서 실행되는 느린 알고리즘 보다 항상 더 빠르다.
또한, 항상 문제의 모든 적법한 인스턴스에 대해 원하는 출력을 반환해야한다.
알고리즘 용어
- problem : 답을 구하는 질문
- parameter : 문제 설명에서 특정 값이 할당되지 않은 변수 - 종종 문제에 대한 입력값
- instance : input parameter에 대한 특정 값의 입력
- algorithm : 문제를 해결하는 단계적 절차
알고리즘의 속도 및 적법성
: 충분히 큰 특정 값의 입력을 가정할 때, 느린 컴퓨터에서 실행되는 알고리즘이 빠른 컴퓨터에서 실행되는 느린 알고리즘보디
항상 더 빠르다.
: 항상 문제의 모든 적법한 인스턴스에 대해 원하는 출력을 반환해야한다. ( 해당 내용의 증명은 귀납법과 모순에 의한 증명이 있다. 아니면 반례(counterexample)을 찾아도 된다.
Analysis of Algorithm Efficiency (알고리즘 분석)
- 다음 가정으로 RAM 모델에서 단계적 절차는 모두 시간이 동일하다고 가정한다.
- 이 모델은 지도와 같은 의미에서 유용하고 정확하다.
- 단순 +,-,*,==,if,call 한번씩 절차를 밟는다.
- 데이터의 크기와 서브루틴의 내용에 따라 달라진다. ex) sort(정렬)은 단순 절차가 아니다.
- 각각의 메모리 접근은 정확히 한번의 절차를 밟는다.
- 또한 필요한 만큼의 메모리가 있다고 가정한다.
Asymptotic Notations
우리가 선호하는 알고리즘 효율성 측정 기준은 worst-case 복잡도이다.
- 알고리즘 분석은 input size 을 변수로 알고리즘의 효율성을 측정한다.
- 알고리즘의 worst_case 시간 복잡도는 알고리즘의 입력 크기 n에 대한 기본 연산의 최대 수행 횟수로 정의된다.
- 알고리즘의 best_case 시간 복잡도는 알고리즘의 입력 크기 n에 대한 기본 연산의 최소 수행 횟수로 정의된다.
왜 점근적 표기를 사용하는가?
- 함수에 대한 정확한 표현이 매우 복잡하고 어렵기 때문!
그래서 함수의 상한선(upper bounds), 하한선(lower bounds)로 표현한다.
대표적인 표기로 빅-오, 빅-오메가, 빅-세타를 사용한다.
[빅오 표기법]
- 빅오 표기법에서는 upper bound를 제공하므로 상한선을 무효화하지 않고, negative term을 버릴 수 있다.
- 두 함수의 합은 지배적인 함수에 의해 결정된다.
- 함수간의 곱에서 두 함수 모두 증가한다 했을 때, 두 함수 모두 중요하다.
예제)
[빅 오메가 표기법]
[빅 세타 표기법]
코드를 입력하세요Simple Programming Analysis
코드를 보며 시간 복잡도를 알아보자!
def selection_sort(arr):
n = len(arr)
# 배열 전체를 순회
for i in range(n):
# 현재 순회 중인 요소를 최소값으로 가정
min_index = i
# 현재 요소의 다음 요소부터 비교를 시작
for j in range(i+1, n):
# 만약 현재 가정한 최소값보다 작은 요소가 있다면
if arr[j] < arr[min_index]:
# 최소값의 위치를 갱신
min_index = j
# 실제로 최소값이 초기 가정과 다르다면 요소의 위치를 교환
arr[i], arr[min_index] = arr[min_index], arr[i]
return arr
# 예제 배열
example_array = [64, 25, 12, 22, 11]
# 선택 정렬 실행
sorted_array = selection_sort(example_array)
# 정렬된 배열 출력
print(sorted_array)
해당 선택 정렬의 시간 복잡도는 O(n^2)이다.
해당 내용을 summation 증명을 통해 분석이 가능하다. 해당 내용은 아래와 같다.
이것을 통해 tight bound로 세타(n^2)이 가능하며, 빅오 + 빅오메가로도 설명이 가능하다.
def insertion_sort(arr):
# 배열의 두 번째 요소부터 시작하여 배열을 순회
for i in range(1, len(arr)):
key = arr[i] # 현재 요소를 key로 설정
j = i - 1 # 비교를 시작할 위치 설정
# key보다 큰 요소들을 오른쪽으로 이동
while j >= 0 and key < arr[j]:
arr[j + 1] = arr[j]
j -= 1
# 적절한 위치에 key 삽입
arr[j + 1] = key
return arr
# 예제 배열
example_array = [9, 5, 1, 4, 3]
# 삽입 정렬 실행
sorted_array = insertion_sort(example_array)
# 정렬된 배열 출력
print(sorted_array)
해당 삽입 정렬의 시간 복잡도는 O(n^2)이다.
-
삽입 정렬의 내부 while 루프 반복 횟수
삽입 정렬에서 각 요소는 이미 정렬된 배열 부분에 적절한 위치를 찾기 위해 왼쪽으로 이동합니다. 이 과정에서 내부 while 루프가 사용됩니다. 이 루프의 반복 횟수는 다음과 같이 두 가지 조건에 의해 결정됩니다: -
- 배열의 경계를 넘어가지 않도록 하는 조건: j > 0
이 조건은 j 인덱스가 배열의 경계를 벗어나지 않도록 합니다. 즉, j가 0보다 클 때만 while 루프가 실행되어야 함을 의미합니다.
- 요소가 적절한 위치를 찾는 조건: s[j] < s[j-1]
이 조건은 현재 요소 s[j]가 바로 앞의 요소 s[j-1]보다 작을 때 계속해서 위치를 조정합니다. 즉, 현재 요소가 앞의 요소보다 크거나 같아지면 반복이 멈추고, 요소가 적절한 위치를 찾은 것으로 간주합니다.
- 최악의 경우 분석
삽입 정렬의 최악의 성능 분석에서는 조기 종료를 고려하지 않고, 이 while 루프가 각 반복에서 최대 i번 실행될 것으로 가정합니다. 여기서 i는 현재 정렬 중인 요소의 인덱스입니다. 예를 들어, 첫 번째 요소 이후에 있는 두 번째 요소는 최대 한 번, 세 번째 요소는 최대 두 번 이동할 수 있습니다.
이러한 분석에 따라 삽입 정렬은 최악의 경우
빅오 (n^2) 의 시간 복잡도를 가집니다. 이는 각 요소에 대해 최대 그 요소 앞에 있는 모든 요소와 비교를 수행할 수 있기 때문입니다. 따라서, 모든 요소가 역순으로 정렬되어 있을 경우가 삽입 정렬의 최악의 시나리오입니다
Asymptotic Dominance
Logarithms
예시 - 이진탐색
def binary_search(arr, target):
low = 0
high = len(arr) - 1
while low <= high:
mid = (low + high) // 2
guess = arr[mid]
if guess == target:
return mid # 타겟 값의 인덱스 반환
if guess > target:
high = mid - 1 # 타겟이 더 작은 경우, 상위 반을 제거
else:
low = mid + 1 # 타겟이 더 큰 경우, 하위 반을 제거
return None # 타겟 값을 찾지 못했을 경우 None 반환
# 예제 사용
my_list = [1, 3, 5, 7, 9]
print(binary_search(my_list, 3)) # 출력: 1
print(binary_search(my_list, -1)) # 출력: None
