알고리즘.시간복잡도

import from 희준님 블로그
https://velog.io/@kler/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%8B%9C%EA%B0%84-%EB%B3%B5%EC%9E%A1%EB%8F%84

시간 복잡도

O(1): 개인의 이름이 있는 페이지와 이름이 주어지면 전화번호를 찾는다.

console.log(“hello”)
console.log(“hello”) // 여러번 (상수번 반복)
console.log(“hello”)
console.log(“hello”)

O(log n): 정렬된 전화번호부에서 절반의 지점을 탐색해 이름을 확인하여 전화번호를 찾기 반복한다.

for (let i = 0; i < n; i = i*2) {
      console.log(“hello”)
  } // log2(n)

O(n): 전화번호에 특정 숫자 7이 포함된 모든 사람을 찾는다. 전화번호가 주어지면 해당 사람을 찾는다.

for (let i = 0; i < n; i++)
for (let i = 0; i < n; i = i + 2)
O(n*logn):

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

O(n^2): 전화번호의 끝에 실수로 0추가 시 0제거.

for (let i = 0; i < n; i++) {
     for (let j = 0; j < n; j++) {
     }
 }

O(n^n): 전화번호를 하나 읽을때 마다 모든 전화번호를 다시 검색한다.

그래프

시간복잡도with indexOf
시간복잡도와 공간복잡도의 개념을 알아야하지 않을까 하는 생각이다.