팀과제: 시간복잡도 Big O 표기법

https://www.youtube.com/watch?v=0xGJx6qsNCY&list=PLsMufJgu5933ZkBCHS7bQTx0bncjwi4PK&index=5 

 

---

 

Big-O표기법

가장 안좋은 입력 worst case input 에 대한 기본 연산횟수를 측정.

알고리즘 수행시간 = 최악의 입력에 대한 기본연산횟수.

기본연산횟수에 대한 자세한 계산방법은 위의 강의영상을 보도록 하자.

 

Big O 표기법은 함수값을 결정하는 최고차항만으로 간단하게 표기한다.

최고차항의 계수(상수)는 생략한다.

 

---

O(1)

O(n^0)를 표시한 것.

 

예컨대 이런 간단한 함수.

function (a) => {return a+1} 

기본연산이 항상 1번뿐이다.

T(n) = 1

T(n) = O(1)

---

O(n)

T1(n) = 2n-1

T2(n) = 4n+1

 

어떤 경우든 표기는 O(n)으로 한다.

T1(n) = O(n)

T2(n)= O(n)

 

함수값을 결정하는 최고차항만으로 간단하게 표기하는 것이 Big O 표기법.

---

O(n^2)

T3(n) = 3/2n^2 - 3/2n + 1

T3(n) = O(n^2)

 

---

O(log n)

function 몇비트일까(n){
    let count = 0;
    while(n>0){
        n = n/2
        console.log(n)
        count+=1
        console.log(count)
    }
    return count;
}

console.log(몇비트일까(8))
//주의 자바스크립트는 위 while 문을 빠져나오는데 무려 1078번 돈다.

자바스크립트에서는 총 1078번의 카운트가 발생한다.

이와 관련해서는 아래의 글 참조.

일단 이해하기로는, 0으로의 점근은 2의 -1075승이 가장 작은 숫자이다.

위의 코드에서는 입력값이 8이므로 1078번 돈 것이다.

 

https://www.exploringbinary.com/glibc-strtod-incorrectly-converts-2-to-the-negative-1075/

GLIBC strtod() Incorrectly Converts 2^-1075 - Exploring Binary

 

---