알고리즘은 뭘까?

• 알고리즘은 어떤 일을 하기 위한 명령의 집합이다. 어떤 목적을 달성하거나 결과물을 만들어내기 위해 거쳐야 하는 일련의 과정들을 의미한다.
• 알고리즘은 각기 다른 모양과 형태를 가지고 있기 때문에 타임 복잡도를 설명하는데 자주 사용된다.
• 시간 복잡도를 분석하는 것은 알고리즘이 문제를 해결하는 데에 어느 정도의 시간이 걸리는 지를 분석하는 것과 같다.
  그리고 이는 Big-O 표기를 사용해 정의할 수 있다.

빅오 표기법

• 빅오 표기법(Big O notation)은 알고리즘이 얼마나 빠른지 표시하는 특별한 방법이다.
• 알고리즘이 동작하기 위해 필요한 연산 횟수를 나타낸다.
• 최악의 실행 시간을 나타내는 빅오 표기법 : O(n)
  -> 단순 탐색의 실행 시간

많이 사용하는 빅오 실행 시간 예시

Regular       Big-O
2             O(1)   --> It's just a constant number
2n + 10       O(n)   --> n has the largest effect
5n^2          O(n^2) --> n^2 has the largest effect

시간 복잡도에서 중요한 것은 정해진 표현식에 가장 큰 영향을 미치는 n의 단위이다.

• O(log n), 로그 시간 : 이진 탐색
• O(n), 선형 시간 : 단순 탐색
• O(n * log n) : 퀵정렬과 같이 빠른 정렬 알고리즘
• O(n²) : 선택 정렬과 같이 느린 정렬 알고리즘
• O(n!) : 정말 느린 알고리즘

정리

• 이진 탐색은 단순 탐색보다 아주 빠르다.
• O(log n)은 O(n)보다 빠르고, 찾으려는 리스트의 원소의 개수가 증가하면 상대적으로 더 빨라진다.
• 알고리즘의 속도는 시간으로 측정하지 않고, 연산 횟수가 어떻게 증가하는 지로 측정한다.
• 알고리즘의 시간은 빅오 표기법으로 나타내며, 어떻게 증가하는가로 측정한다.