알고리즘 | 알고리즘 표기법

✔ 학습목표 알고리즘 실행 시간의 상한과 하한을 표기할 수 있다. 알고리즘의 효율성 프로그램을 작성한 후에 실행하면 작업이 완료될 때까지 어느 정도 시간이 걸린다. 처리하는 데이터가 많아지고, 작업이 복잡해질수록 이 시간은 매우 중요하다. 그래서 알고리즘의 시간 효율성과 공간 효율성(메모리)을 나태 내기 위해 표기법을 사용한다. 두 가지 효율, 즉 시간 복잡도와 공간 복잡도를 나타내는 방법으로는 빅오(Big O), 빅오메가(big Ω),빅세타(big Θ) 표기법이 있다. 강의에서는 빅오와 빅오메가를 다룬다. Big O Big O는 알고리즘 실행 시간의 상한, 쉽게 말하자면 최악의 복잡도를 나타낸다. 복잡도를 비교하자면 다음과 같다. 앞서 배운 검색 알고리즘을 생각해보면 선형검색은 O(n), 이진 검색은 ..

2021.02.04