Big-O
알고리즘의 시간, 공간복잡도를 표기하는 방법
입력의 크기와 수행시간의 관계
더 나은 코드란?
- 코드가 수행되는 데 시간이 적게 걸리는 것.
- 메모리를 적게 사용하는 것.
- 코드의 가독성이 좋은 것(최대한 적은양의 코드면 좋겠다).
Big-O의 필요성
문제를 해결할 때 여러가지의 방법들이 있는데,
그 방법들을 서로 비교하고 성능을 평가하기 위해 필요하다.
불필요한 연산을 제거하여 알고리즘 분석을 쉽게 할 목적으로 사용된다.
"1에서부터 특정한 N값이 있을 때, 1과 N을 포함한 사이에 있는 모든 숫자들을 더하라" 는 문제가 있다고 해보자.
1. 생각하기 쉬운 해결법
function addUpTo(n) {
let total = 0;
for (let i = 1; i <=n ; i++) {
total += i;
}
return total;
};2. 단순해진 해결법
function addUpTo(n) {
return n * (n+1) / 2;
}-> Loop를 사용하지 않았고, 코드가 매우 간단해졌다.
✔︎ 코드 수행 시간을 알 수 있는 함수
아래 코드를 사용하여 수행 시간을 확인 할 수 있다.
let t1 = performance.now();
addUpTo(1000000000)
let t2 = performance.now();
console.log(`Time Elapsed: ${(t2 - t1) / 1000} seconds.`)→ 하지만 단순히 코드 실행 시간으로만 성능을 판단하기에는 하드웨어 또는 프로그래밍 언어에 따라 편차가 크게 달라지기 때문에 명령어의 실행 횟수만을 고려한다.
연산들의 갯수 카운팅해보기
function addUpTo(n) {
return n * (n+1) / 2;
}🔺 곱셈, 더하기, 나눗셈 연산이 있다. 숫자는 포함하지 않는다. 연산은 3번 이루어진다.
function addUpTo(n) {
let total = 0;
for (let i = 1; i <=n ; i++) {
total += i;
}
return total;
};🔺 연산자가 loop안에 있으므로 n갯수 만큼 연산이 늘어나게 된다.
시간 복잡도
시간 복잡도(Time Complexity)는 알고리즘의 절대적인 실행 시간을 나타내는 것이 아닌 알고리즘을 수행하는데 연산들이 몇 번 이루어지는지를 숫자로 표기한 것이다.
시간복잡도의 가장 간단한 정의는 알고리즘의 성능을 설명하는 것이다.알고리즘을 수행하기 위해 프로세스가 수행해야하는 연산을 수치화 한것이다.
1 O(1) --> 상수, n에 영향을 받지 않는다.
n + 3 O(n) --> 선형적으로, n값에 비례한다.
n^3 O(n^2) --> n값의 제곱의 영향을 받는다. 실행시간이 가장 최대치이다.>O(1) – 상수 시간 : 문제를 해결하는데 오직 한 단계만 처리함.
O(log n) – 로그 시간 : 문제를 해결하는데 필요한 단계들이 연산마다 특정 요인에 의해 줄어듬.
O(n) – 직선적 시간 : 문제를 해결하기 위한 단계의 수와 입력값 n이 1:1 관계를 가짐.
O(n log n) : 문제를 해결하기 위한 단계의 수가 N*(log2N) 번만큼의 수행시간을 가진다. (선형로그형)
O(n^2) – 2차 시간 : 문제를 해결하기 위한 단계의 수는 입력값 n의 제곱.
O(C^n) – 지수 시간 : 문제를 해결하기 위한 단계의 수는 주어진 상수값 C 의 n 제곱.✨ O(1) 입력에 관계없이 복잡도는 동일하게 유지된다.
function addUpTo(n) {
return n * (n+1) / 2;
}✨ O(n) 입력이 증가하면 처리시간 또는 메모리 사용이 선형적으로 증가한다.
function addUpTo(n) {
let total = 0;
for (let i = 1; i <=n ; i++) {
total += i;
}
return total;
};✨ O(n)
function countUpAndDown(n) {
console.log("Going up!");
for (let i = 0; i < n; i++) {
console.log(i);
}
console.log("At the top\nGoing down...");
for (let j = n - 1; j >= 0; j--) {
console.log(j);
}
console.log("Back down. Bye!");
}✨ O(n^2)
function printAllPairs(n) {
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
console.log(i, j);
}
}
}시간복잡도를 구하는 요령
- 하나의 루프를 사용하여 단일 요소 집합을 반복 하는 경우 : O (n)
- 컬렉션의 절반 이상 을 반복 하는 경우 : O (n / 2) -> O (n)
- 두 개의 다른 루프를 사용하여 두 개의 개별 콜렉션을 반복 할 경우 : O (n + m) -> O (n)
- 두 개의 중첩 루프를 사용하여 단일 컬렉션을 반복하는 경우 : O (n²)
- 두 개의 중첩 루프를 사용하여 두 개의 다른 콜렉션을 반복 할 경우 : O (n * m) -> O (n²)
- 컬렉션 정렬을 사용하는 경우 : O(n*log(n))
공간복잡도
프로그램을 실행 및 완료하는데 필요한 저장공간의 양을 뜻함
✨ total, i 변수가 공간에 영향을 준다. O(1)
function sum(arr) {
let total = 0;
for (let i = 0; i < arr.length; i++) {
total += arr[i];
}
return total;
}✨ 공간은 arr의 길이에 비례해서 커지게 된다. O(n)
function double(arr) {
let newArr = [];
for (let i = 0; i < arr.length; i++) {
newArr.push(2 * arr[i]);
}
return newArr;
}