C - Big-O 표기법

1. g(n)=1
	- 상수 시간 복잡도
    - f(n) = O(1)
    - 입력이 증가해도 항상 일정한 시간이 걸리는 경우
    - 가장 이상적인 성능
    
void f(int n) { //n은 입력의 크기
	printf("Hello");
}
//어떠한 크기의 n이 들어올지라도 "Hello"한번 찍어주고 프로그램을 끝냄
//n이 몇이던지 자신의 일을 수행하는데 걸리는 시간은 1로 일정함

void f(int n) {
	printf("Hello");
	printf("World");
}
//어떠한 크기의 n이 들어올지라도 "Hello" 한번 "World" 한번 찍어주고 프로그램을 끝냄
//n이 몇이던지 자신의 일을 수행하는데 걸리는 시간은 2로 일정함

2. g(n)=n
	- 선형 시 간 복잡도
    - f(n) = O(n)
    - 시간은 입력의 크기에 비례해서 증가함
 
void func(int n) {
	int i = 0;
	while (i < n) {
		printf("hello");
		i++;
	}
}

//n의 크기 만큼 hello를 출력함

void func(int n) {
	int i = 0;
	while (i < n) {
		printf("hello");
        printf("world");
		i++;
	}
}

//n의 크기 만큼 hello와 world를 출력함

결론 = n에 비례해서 증가한다.
- 이 알고리즘의 시간 복잡도는 O(n)이야 = n이 커지는 만큼 커지겠군

3. g(n)=n^k
	- 다항 시간 복잡도
    - f(n) = O(n^2), if k = 2
    - 시간은 입력의 크기의 k제곱에 비례해서 증가함
    
void func(int n) {
	int i = 0, j = 0;
	for (i = 0; i < n; i++) {
		for (j = 0; j < n; j++) {
			printf("hello");
		}
	}   
    
//n^2번씩 증가하므로 n=1 -> 1 n=10 -> 100, n=100 -> 10000 등..
//for loop를 중첩시키는 것을 주의해야함. 3~4번 혹은 그 이상을 진행시키면 시간이 훨씬 더 많이 걸리기 때문이다.

ex) n명인 반의 학생들이 모두 키 순으로 앉아있다. 새로운 전학생이 한명 왔을때 앉히는 방법은 3가지다
	1. 그냥 맨 앞에 앉아 = 학생이 몇명이건 상관없이 맨 앞에 앉으면 되기 때문이고 Big-O표기법으론 O(1)이다.
    2. 네 키에 맞게 자리를 찾아서 앉아 = 모든 학생들과 한번씩만 비교하면 되기에 Big-O표기법으론 O(n)이다.
    3. 새로 한명이 왔으니 키 순서를 다시 정하자 = 서로서로 한사람씩 번갈아가며 비교를 하는거니 n(n-1)
    Big-O표기법으론 O(n^2)이다.
    
    
 4. g(n)=k^n
 	- 지수 시간 복잡도
    - f(n)=o(2^k), if k=2

int func(int n) {
	if (n == 0)
		return 0;
	if (n == 1)
		return 1;

	return func(n - 1) + func(n - 2);
}
// n=1 -> 2, n=10 -> 2^10, n=100 -> 2^100 .....
//이 시간 복잡도는 사용하기 힘든 코드다 데이터가 빠르게 증가하기 때문에 시간 복잡도를 줄이는 노력이 필요하며
//이를 위해서 피보나치수열의 시간 복잡도도 Big-O의 이걸 훨씬 줄이는 방법이 개발됨

5. g(n)=logk n
	- 로그 시간 복잡도
    - f(n)=o(log n), if k=2
    - 시간은 n의 log에 비례해서 증가하며
    - 밑 k는 상관이 없다
    
int func(int n) {
	for (k = 1; k < n; k = k * 10) {
		printf("hello");
	}
}    
//loop가 회전하는 횟수가 n이 된다는 얘기로 결국 k는 log10n만큼 수행 됨
// n=1 -> 0, n=10 -> 1, n=100 -> 2, n=1000 -> 3 ...
// 시간 복잡도가 증가하는 속도가 느려서 좋다
// 로그 시간복잡도는 상수 시간 복잡도 다음으로 성능이 좋은 시간 복잡도로 생각됨

6. g(n) = n log n
//n의 어떤 log n이 곱해져있기 때문에 직선보다는 조금더 시간이 걸리는 형태

void func(int n) {
	for (i = 1; i <= n; i++) {
		for (j = 1; j <= n; j *= 10) {
			printf("hello");
		}
	}
}
// n=1 -> n*log n의 관점으로 0, 1, 2, 3, 4등 ... 으로 증가

	-

가능한 내가 짠 알고리즘이나 소프트웨어 시간 복잡도가 왼쪽으로 오게 해야함.