[TIL 프로젝트] 9일차 - 시간 복잡도 1

빅오 표기법은 알고리즘의 시간복잡도나 공간복잡도를 표현할 때 사용되는 수학적 표기법
입력 크기 n에 대해 가장 지배적인 연산 횟수(성장률)를 수학적으로 표현한 것으로 최악의 경우 기준으로 표현함

a = arr[0] 의 경우 입력 크기와 관계없이 항상 일정한 시간으로 O(1)
이진 탐색의 경우 입력을 절반씩 줄이기 때문에 O(log n)
선형 탐색의 경우 한 번씩 다 훑기 때문에 O(n)
머지 정렬의 경우 거의 모든 효율적인 정렬로 O(n log n)
중첩 반복문의 경우 O(n^2)
재귀 조합의 경우 O(2^n)
완전탐색(순열)의 경우 모든 경우의 수를 탐색하기 때문에 O(n!)

O(n+n^2)의 경우 n^2가 n보다 훨씬 빨리 커짐으로 빅오 표기법으로는 O(n^2)로 표기함

void example1(int n){
	for(int i=0; i<n;i++){
		cout << i << endl;
	}
}

시간 복잡도는 O(n)

void example2(int n){
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			cout<<i+j<<endl;
		}
	}
}

시간 복잡도는 O(n^2)

void example3(int n){
	for(int i=0;i<n;i++){
		for(int j=0;j<5;j++){
			cout<<i+j<<endl;
		}
	}
}

시간 복잡도는 O(n)
안쪽 루프의 경우에는 5까지만 작동하기 때문에 무시함으로 O(n)

void example4(int n){
	int i=1;
	while(i<n){
		cout<<i<<endl;
		i*=3;
	}
}

시간 복잡도는 O(log n)
i *=3 은 3배씩 증가해서 반복 횟수는 log3(n)

void example5(int n){
	if(n==0) return;
	cout<<n<<endl;
	example5(n-1);
}

시간 복잡도는 O(n)
한번 호출마다 1씩 줄어들어서 총 n번 호출

void recur(int n){
	if(n==0) return;
	recur(n-1);
	recur(n-1);
}

시간 복잡도는 O(2^n)
이진 트리처럼 퍼지기때문에 총 호출수는 2^n-1 번