빅오 표기법 규칙

Lee Dong Uk·2021년 6월 19일

계수 법칙

계수 법칙은 단순히 입력 크기와 연관되지 않은 상수를 전부 무시하면 된다.
빅오에서 입력 크기가 클 때 계수를 무시할 수 있다는 뜻이다.

	상수 k>0 인 경우 f(n) 이 O(h(n)) 이면 kf(n) 은 O(h(n)) 이다

이는 7f(n) 과 f(n) 둘 다 동일한 O(f(n) 이라는 빅오 표기법을 지님을 의미한다.

다음은 시간 복잡도 O(n) 을 지닌 코드의 예다.

const a =(n)=> {
	let cnt  = 0 
    for(let i =0;i<n;i++){
    	cnt ++
    }
    return cnt
}

위 코드는 f(n) 의 시간 복잡도는 n 이다

const a =(n)=>{
	let cnt  = 0 
    for(let i =0;i<5*n;i++){
    	cnt ++
    }
    return cnt
}

위 코드의 시간 복잡도는 5n 이다 0 부터 5n까지 실행하기 때문이다.

하지만 위의 두 코드 모두 O(n) 의 빅오 표기법을 지닌다.

간단히 말해 n이 무한대로 커질 때 연산이 추가적으로 존재한다고 해서 달라지는 것은 없기 때문이다.
n이 충분히 클 때 위의 코드가 n번 수행된다고 할 수 있다.

이 처럼 빅오 표기법에서 모든 상수는 생략 가능하다.

추가로 시간 복잡도가 n+ k 인 경우 k도 생략 가능하다.

합의 법칙은 쉽게 이해할 수 있다. 시간 복잡도를 더할 수 있다는 것이다.

두 개의 다른 알고리즘을 포함하는 상위 알고리즘이 있다고 가정하면, 해당 상위 알고리즘의 빅오 표기법은 두 개의 알고리즘의 합이다.

	fn(n) 이 O(h(n)) 이고 g(n) 이 O(p(n)) 이라면 f(n) + g(n) 은 O(h(n)+p(n)) 이다.

합의 법칙을 적용한 다음 계수 법칙을 적용해야 한다는 점에 주의한다.

const a = (n) =>{
	let cnt = 0
    for(let i =0;i<n;i++){
    	cnt++
    }
    
    for(let i =0;i<5* n;i++){
    	cnt++
    }
    
    return cnt

위의 예시에서 세 번째 줄의 시간 복잡도는 n 이고 다섯 번째 줄의 시간복잡도는 5n 에 해당한다.
이로 인해 결괏값은 6n 이다. 하지만 계수 법칙을 적용하면 최종 결과는 O(n) 이 된다.

곱의 법칙은 빅오가 어떤 식으로 곱해지는지에 관한 것이다.

	f(n) 이 O(h(n)) 이고 g(n) 이 O(p(n)) 이면 f(n)g(n) 은 O(h(n)p(n)) 이다.

다음 코드는 두 개의 중첩 for 루프를 포함하며 해당 중첩 for 루프에 곱의 법칙이 적용된다.

const a= (n)=>{
	let cnt = 0
    for(let i =0;i<n;i++){
    	cnt++
        for(let j =0;j<n;j++){
			cnt++
        }
    }
    return cnt
}

위의 예에서 시간 복잡도는 5n*n 이다. 다섯 번째 줄이 내부 루프에 의해 5n번 실행되고 내부 루프가 외부 루프에 의해 n번 실행되기 때문이다.
따라서 결과는 5n^2 번 연산이 일어나고 계수 법칙을 적용한 최종 결과는 O(n^2)이 된다.

다항 법칙은 다항 시간 복잡도가 동일한 다항 차수를 지닌 빅오 표기법을 지님을 나타낸다.
????

f(n)이 k차 다항식이면 f(n^k)