좋은 알고리즘이란?
상황에 따라 달라집니다.
- 메모리를 최소화하길 원하면, 메모리를 적게 사용하는 알고리즘이 더 좋은 알고리즘이 되고,
- 최고의 속도를 원한다면 빠른 알고리즘이 성능이 좋은 알고리즘이 될 것 입니다.
대부분 성능이 좋은 알고리즘을 선호할 것이고 알고리즘의 속도를 성능의 척도로 사용하고
이를, 시간 복잡도라고 부릅니다.
시간복잡도란?
특정 알고리즘이 어떤 문제를 해결하는데 걸리는 시간을 말합니다.
하지만
시간을 측정해서 알고리즘을 평가하기에는 사용자마다 PC의 성능이 다릅니다.
따라서 알고리즘을 평가할 때는 시간을 측정하는 방식보다는 코드에서 성능에 영향을
미치는 영향을 찾아 실행시간을 예측합니다.
그것은, 반복문 입니다.
반복문이 여러 번 반복될수록 실행시간이 길어집니다.
알고리즘의 선응은 알고리즘 반복문을 보고 성능을 평가합니다.
예시
1 ,2 ,3, 4숫자에서 3을 찾는다면?
3을 찾기 위해서는 배열의 0번 인덱스부터 차례대로 찾을 것입니다.
1, 2, 3, 4순으로 검사해서 3을 세 번째만에 찾아내게 됩니다.
- 어떨 때는, 한 번에
- 어떨 때는 배열의 길이 만큼 순회해서
- 어떨 때는 중간에서 찾게 됩니다.
최선의 경우 : Big-Ω (빅-오메가)
최악의 경우 : Big-O (빅-오)
평균의 경우 : Big-Θ (빅-세타)
이 중, 최악의 경우를 평가하는 Big-O를 자주 사용합니다.
Big-O 알고리즘 성능 평가
[1, 2, 3, 4] 배열의 첫 번째부터 마지막까지 비교하면서 찾기 때문에 최악의 경우 찾는 데이터가
가장 마지막에 있는 경우 입니다.
만약,
배열의 데이터가 총 n개 있다면 이 알고리즘은 최악의 경우 n번만의 데이터를 찾을 수 있습니다.
이를 Big-O표기법으로 O(n)이라고 표현합니다.
예시
- 배열의 길이가 4라면, 최악의 경우 4번만에 데이터를 찾음.
- 배열의 길이가 5라면, 최악의 경우 5번만에 데이터를 찾음.
- 배열의 길이가 16라면, 최악의 경우 16번만에 데이터를 찾음.
- 배열의 길이가 n이라면, 최악의 경우 n번만에 데이터를 찾음.
데이터 수를 나타내는 n에 1를 넣으면 1, 5를 넣으면 계산량은 5가 됩니다.
데이터가 많아지면 비례해서 계산량이 많아집니다.
이러한 이유로 O(n)의 알고리즘은 선형시간 알고리즘이라고 부릅니다.
Big-O 표기법은, 입력이 늘어날 때 계산량이 늘어나는 척도를 나타내기 위한 것입니다.
