Big-O?
하나의 문제에 해결법은 너무나도 많다.. 여러가지 방법으로 풀이하는데 여기서 가장 좋은 해결방법은 무엇일까? 이것이 빅O의 핵심이다. 코드를 비교하고 성능을 평가하는 방법.
Big-O를 통해 코드의 효율성을 분류 할 수 있게 된다. 효율성의 지표로는 시간에 대한 개념인 시간 복잡도, 공간에 대한 개념인 공간 복잡도가 있다.
- 시간복잡도 : 입력한 N의 크기에 따라 실행되는 조작의 수
- 공간복잡도 : 알고리즘이 실행될때 사용되는 메모리의 양
시간 복잡도의 표현
시간 복잡도는 알고리즘에 입력한 N의 크기에 따라 수행 시간이 얼마인지를 나타낸다.
다양한 방법으로 시간 복잡도를 표현하지만 자주 사용되는 것들은 아래와 같다.
- O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!) < O(nⁿ)
**오른쪽으로 갈수록 비효율적이다.
시간 복잡도의 비교
코드를 비교할 때 단순히 시간을 비교하는 것에는 문제가 있다.
n을 입력받아 n까지 계속 더하는 함수를 만들고 실행되는 시간을 출력해보았다(※ 시간을 측정하는데 정확한 방법은 아님)
같은 컴퓨터에 코드를 추가 하지않고 같은 숫자를 입력받아서 출력해보았는데도 계속해서 시간이 다르다
밑에는 위의 add 함수와 같이 n까지 더하는 다른 방법의 알고리즘이다.
function add(n) {
return n * (n + 1) / 2;
}for문을 사용했을 때 보다 실행의 시간은 빨라지지만 여전히 실행할때마다 달라진다
이 예제들에서 중요한것은 단순히 시간만으로 비교한다는것은 완전히 믿을 수 없다는 것이다.
엄청나게 오래 걸리는 코드들을 갖고 실행 시간을 알아보기 위해서 테스트를 계속해서 실행할 수는 없다. 이렇게 테스트를 하지않아도 코드를 비교하는 방법, 그 방법이 바로 Big-O표기이다.
시간복잡도 연산
같은 컴퓨터, 같은 사양이라도 시간은 계속해서 달라진다. 그럼 어떻게 측정해야 할까?
초를 세는것 대신에 컴퓨터가 처리해야하는 연산 개수를 세면 된다. 환경이 달라지는 변수에 상관없이 객관적으로 측정할 수 있을것이다.
return n * (n + 1) / 2;위 코드에서 연산은 3개다. *와, +, /, 숫자들은 연산에서 제외한다.
입력받은 n이 1억이든 10억이든 n과 상관없이 연산은 3번으로 끝이난다.
n과 상관없이 일정한 시간이 걸리는것을 O(1)으로 표현한다.
function add(n) {
let sum = 0;
for( let i=1; i<=n; i++) {
sum += i;
}
return sum;
}
add 함수의 연산은 몇개일까? sum을 더할때 +의 연산을 한번하는데, for문안에 있기 때문에 n번 연산한다. 이뿐 아니라 sum += i에서 =도 n번, i++에서도 2번의 n, i<=n에서도 n번, sum을 초기화하는 1번의 연산, i를 초기화하는 1번의 연산, 총 5n+2이다. 따라서 O(5n+2)가 된다.
상수항 무시
Big-O는 상수항, 영향력 없는 항에 큰 의미를 두지 않는다. 궁극적으로 그래프를 그렸을때 전체적인 추세를 보는것이기 때문에 상수항은 크게 의미가 없다. 위 O(5n+2) 결과가 나온것에 상수항을 무시할 수 있다.
따라서 O(5n + 2) 결과에서 n이든 5n이든 +2를하든 이런 사소한것들은 무시한다. O(5n + 2)는 O(n)으로 표현한다.
O(n² + 5) => O(n²)
O(10n + 10) => O(n)
영향력이 없는 항 무시
O(n + 1000000) => O(n)
O(n²+5n) => O(n²)
공간 복잡도
공간복잡도는 입력에 상관없이 메모리의양, 알고리즘 자체가 차지하는 공간을 나타낸다.
function sum(arr) {
let total = 0 ;
for (let i = 0; i < arr.length; i++) {
total += arr[i]
}
return total;
}arr를 받아서 합을 계산하는 함수이다. 공간 복잡도는 시간은 상관없으므로 공간만 보면된다.
return 받을 total의 변수(숫자) 하나와 i를 초기화해준 공간 하나가 끝이다.
배열의 크기에 상관없이(입력의 크기) total 변수 하나에만 더해주기 때문에 상수의 공간이다. 따라서 O(1)이다.
function double(arr) {
let newArr = [];
for(let i = 0; i < arr.length; i++) {
newArr.push(2 * arr[i]);
}
return newArr;
}새로운 배열을 할당한 후 입력받는 arr의 크기에따라 newArr의 크기도 달라진다.
arr배열의 입력에 비례해서 newArr의 크기가 달라지는것이다. 새 변수를 할당하는 공간은 무시되고 따라서 O(n)이다.
자료구조의 Big-O
