[알고리즘]시간 복잡도

계산 복잡도 이론에서 시간 복잡도는

문제를 해결하는데 걸리는 시간과 입력의 함수 관계를 가리킨다.

 

컴퓨터과학에서 알고리즘의 시간복잡도는

입력을 나타내는 문자열 길이의 함수로서 작동하는 알고리즘을 취해

시간을 정량화하는 것이다.- 위키백과

---

점근 표기법(asymptotic notation)은 어떤 함수의 증가 양상을

다른 함수와의 비교로 표현하는 수론과 해석학의 방법이다. 

알고리즘의 복잡도를 단순화할 때나 무한급수의 뒷부분을 간소화할 때 쓰인다.

 

• 빅 O 표기법 : 최악의 실행 시간을 표기
• 빅 오메가(Ω) 표기법 : 최상의 실행 시간을 표기
• 빅 세타(Θ) 표기법 : 평균 실행 시간을 표기

 

https://ko.wikipedia.org/wiki/%EC%A0%90%EA%B7%BC_%ED%91%9C%EA%B8%B0%EB%B2%95

---

상대적인 성능을 표현한 자료

for (let i = 0; i < navigator; i += 1) {} // O(n)

for (let i = 1; i <= n; i *= 2) {} // O(log n)

for (let i = 0; i < n; i += 2) {
  for (let j = 1; j <= n; j * +2) {}
} // O(n log n)

for (let i = 0; i < n; i += 1) {
  for (let j = 0; j < n; j += 1) {}
} // O(n²)

---

선형시간 :

입력받은 크기만큼 루프를 도는 시간.

for (let i = 0; i < navigator; i += 1) {} // O(n)

const arr1 = [];
for(let i = 1; i<=5; i++) {
arr1.push(i);
}

const arr2 = Array.from({length: 5}, function(v,k) {
return k+1;
})

// n이 루프길이 일때 둘 다 O(n)

---

로그시간 :

loop를 씌운 만큼만 도는 시간.
for (let i = 1; i <= n; i *= 2) {} // O(log n)

---

선형지수시간 :

선형시간에 지수를 곱한 시간.
for (let i = 0; i < n; i += 2) {
  for (let j = 1; j <= n; j * +2) {}
} // O(n log n)

---

2차시간 :

n 의 제곱만큼만 루프를 도는 시간.
for (let i = 0; i < n; i += 1) {
  for (let j = 0; j < n; j += 1) {}
} // O(n²)

 

 

// 지수시간이 팩토리얼시간은 특정한 상황이아니면 가급적 사용을 지양하는것이 좋다.

---

// 빅오표기법은 시간복잡도를 나타내는 표기법 중 하나.

 

빅오표기법의 네가지 법칙

• 계수법칙 : n이 무한에 가까울 수록 k의 크기는 의미가 없기때문에 생략하여 표기한다.
• 합의 법칙 : 빅오끼리 합해질수있다
• 곱의법칙 : 빅오끼리 곱해질 수 있다
• 다항법칙 :  f(n)이 4차 다항식이면 f(n)은 O(n⁴)

주의할 점!

 

1.상수항 무시

2.가장 큰 항 외엔 무시

 

점근적 표기법을 따르기 때문.

---

따라서 

O(n²+100), O(2n - 30), O(4 log n)

는 아래와 같다.

O(n²), O(n), O(log n)

 

 

자바스크립트에서 성능측정방법 :
Date 객체를 이용!!

const start = new Date().getTime();

const end = new Date().getTime();
console.log(end - start);

끝에서 시작 시간을 빼면 작동 시간을 알 수 있기 때문!

 

---

https://school.programmers.co.kr/learn/courses/13213/13213-%EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B8-%EA%B4%91%ED%83%88-%EB%B0%A9%EC%A7%80-a-to-z-javascript