어떤 기능을 하는 코드가 작동하는데 아무 이상이 없다면 코드 퀄리티가 좋다고 장담할 수 없습니다. 똑같은 기능을 하는 다른 코드가 실행되는 시간이 더 짧다면, 혹은 사용하는 메모리가 더 적다면 그제서야 코드 퀄리티가 좋다고 얘기할 수 있을겁니다.
코드 퀄리티
: 이해하기 쉬운 직관적인 코드를 코드 퀄리티가 좋다고 얘기 할 수 있겠지만, 저희는 알고리즘을 배우는 목적을 지니므로 위에서 언급한 실행되는 시간과, 메모리를 사용하는 공간 중 실행되는 시간에 집중하겠습니다.
코드 실행 시간
코드가 실행 되는 시간은 누구나 똑같지 않습니다. PC 사양에 따라서, 혹은 인터넷 등등 많은 환경의 간섭을 받고, 같은 환경이라고 해도 실행되는 시간은 항상 일정하지 않습니다. 그래서 실행 되는 시간을 가지고 비교하기엔 쉽지 않습니다. 그렇다면 코드 실행 시간이 아닌, 컴퓨터가 처리해야할 연산의 개수로 비교하면 어떨까요? 어느 환경에서든지 코드의 변경이 없다면 컴퓨터가 처리해야할 연산의 개수는 일정합니다.
빅오 표기법 (Big-O notation)
: 빅오는 처리해야할 연산의 개수를 대략적으로 세는 표현법입니다.
시간 복잡도를 빅오 표기법에 따라 그래프로 구현한 이미지입니다.
이런 식으로 함수의 형태에 따라 시간 복잡도를 비교해보면 다음과 같습니다.
상수함수 < 로그함수 < 선형함수 < 다항함수 < 지수함수
O(1) < O(log n) < O(n) < O(n log n) < O(n제곱) < O(2의 n제곱)
함수 형태에 따른 실행 시간을 그래프화 시킨 것입니다. 이 이미지에선 선형함수까지만 그래프에서 확인 할 수 있습니다.
빅오 표현법 예시
알고리즘 문제를 풀다보면 주로 마주치는 예시들입니다.
1. O(1) : 스택에서 Push, Pop
2. O(log n) : 이진트리
3. O(n) : for 문
4. O(n log n) : 퀵 정렬, 병합 정렬, 힙 정렬
5. O(n제곱): 이중 for 문, 삽입정렬, 거품정렬, 선택정렬
6. O(2의 n제곱) : 피보나치 수열
