알고리즘의 복잡도 (Complexity of Algorithms)

방법(method)이란 어떤 목적을 달성하기 위해 해야 할 작업을 명확하게 지시한 것입니다.
그리고 방법 중에서도 작업의 횟수가 항상 유한한 것을 특별히 알고리즘(algorithm)이라고 부릅니다.
<한 권으로 그리는 컴퓨터 과학 로드맵> 55p

 

알고리즘의 복잡도는 크게 시간 복잡도(time complexity)와 공간 복잡도(space complexity)로 나뉜다.

알고리즘의 복잡도란 이 알고리즘이 얼마나 복잡한가를 나타내는 것이 아니라

데이터의 개수(문제의 크기), N에 따라 얼마나 많은 시간(공간 : 메모리 용량)을 소요하는가를 나타내는 척도이다.

Big-O 표기법은 최악의 경우 (worst-case)에 대하여 표기하며, 최악의 경우라도 이정도의 성능은 보장한다는 뜻이다.

(따라서 O(N)인 알고리즘이라고 하더라도 소요시간이 O(N)보다 더 짧을 수도 있음 : best case)

 

• 좋은 알고리즘 복잡도 : O(log N), O(N * log N)
• 나쁜 알고리즘 복잡도 : O(N^2), O(2^N) 등등

출처 : https://velog.io/@qksud14/Algorithm-BigO