시간복잡도는 알고리즘의 성능을 나타내는 척도,
시간복잡도: 특정한 크기의 입력에 대하여 알고리즘의 수행 시간 분석
동일한 기능을 수행하는 알고리즘이 있다면, 일반적으로 복잡도가 낮을수록 유리하다.

빅오표기법(Big-o notation)

• 가장 빠르게증가하는 항만을 고려하는 표기법이다.
• 함수의 상한을 나타낸다.
• 예를 들어 연산 횟수가 3n^3 + 5N^2 + 1,000,000인 알고리즘이 있다고하자
  • N이 증가함에 따라서, 3N^3을 제외한 다른 항의 영향력은 작아진다.
• Big-O 표기법에서는 차수가 가장 큰 항에서 계수를 제외하여 n^3으로 표기함
  

아래쪽으로 갈수록 더 안좋은 알고리즘이다.

let array = [1,2,3,4,5] //5개의 데이터
let summary = 0;

for (let i = 0; i<array.length; i++){
  summary += array[i];
}

//console.log(summary)

• 수행 시간은 데이터의 개수 N에 비례할 것임을 예측할 수 있다.
• 시간복잡도는 O의 N이다.

2중 반복문 예제

let array = [1,2,3,4,5]
for(let i=0; i<array.length; i++){
for(let j = 0; j<array.length; j++){
let temp = array[i] * array[j];
console.log(temp)
}
}

• 시간복잡도: O(N^2)
• 하지만 모든 2중 반복문이 시간복잡도가 O(N^2)인 것은 아니다.
• 소스코드가 내부적으로 다른 함수를 호출한다면 그 함수도 고려해야 한다.

알고리즘 설계 Tip

• 일반적인 CPU 기반의 개인 컴퓨터나 채점 목적의 컴퓨터를 고려해보자.
• 자바스크립트를 기준으로 1억 번의 연산을 처리하기 위해 1~5초가량의 시간이 소요
• O(n^3)의 알고리즘을 설계한 경우, N의 값이 5,000이 넘는다면 얼마나 걸릴까?
  • 125억번정도인데 즉, 100초 정도
• 통상 시간제한이 5초정도인데 제한 시간을 5초라고 생각하도 문제를 푸는 것이 합리적이다.

이렇게 푸는 것이 합리적