시간복잡도 빠르기 순서
[fast] O(1) < O( log n ) < O(n) < O(n log n) < O(n^2) < O(n^3) [slow]

O(1)

void Constant(arr){
	printf(arr[0]);
    printf(arr[0]);
}

입력값의 크기에 상관없이 실행시간이 일정한 경우 O(1), 상수는 무시한다.

---

O(n)

예제 1)
void Linear(n){
	for(int i=0;i<n;i++){ //n+1 만큼 반복
    	print(i); //n 만큼 반복
    }
}

(n+1) + n = 2n+1 => O(n), 계수-상수 무시
for문은 마지막 조건문 검사까지 수행하므로 for문 내 코드들 보다 한 번 더 실행됨.

예제 2)
void Linear2(n){
	for(int i=0;i<n/2;i++){ //n/2+1 만큼 반복
    	print(i); //n 만큼 반복
    }
}

n/2 번 반복해도 똑같이 O(n)이다.
1/2 x n 과 같기에 1/2을 계수로 보고 무시한다.

---

O(n²)

1. 중첩 for문이 대표적인 예시다.

void Qudratic(n){
	for(int i=1;i<n;i++){ //n번 반복
    	//중첩 for문이기 때문에 아래 for문이 n*n번 반복한다.
    	for(int j=1;j<n;j++){ //n번 반복
     		printf("안녕?"); //n-1번 반복
     	}
    }
}

i 기준의 for문 반복이 j 기준의 for문을 또 돌리기 때문에 두 for문의 반복 수를 곱한 것과 같은 시간 복잡도가 나온다.

n+(nx(n+n-1)) = 2n² => O(n²)

2. 중첩된 구조이지만 반복 횟수가 매번 변하는 예시

<의사코드>

sample5(A[],n){
	sum <- 0;
    for i<-1 to n-1
    	for j<-i+1 to n
        	sum <- sum+A[i]*A[j];
    return sum;
}

바깥 for 루프에서 i=1일 때, 안쪽 for 루프가 n-1회 반복되고,
바깥 for 루프에서 i=2일 때, 안쪽 for 루프가 n-2회 반복되고,
...
마지막으로 바깥 for 루프에서 i=n-1일 때, 안쪽 for 루프가 1회 반복된다.
따라서, 총 반복횟순는 (n-1)+(n-2)+...+2+1 = n(n-1)/2 가 되어 O(n²)

---

O(n³)

1. 삼중 for문의 경우 O(n^3) 이다.

2. 다른 예시

<의사코드>

sample4(A[], n){
	sum <- 0;
    for i<-1 to n
    	for j<-1 to n {
        	k<-A[1...n]에서 임의로 n/2개를 뽑을 때 이들 중 최대값;
            sum<-sum+k;
        }
    return sum;
}

이중 for문으로 n²번 반복하면서,
크기가 n인 배열에서 n/2개를 뽑으면서 이들 중 최대값을 구하는 것은 n/2에 비례하는 시간이 소요되므로 n에 비례하는 시간이다.
따라서 총 O(n³)

---

O(log n)

O(log n)은 밑이 2인 log2 n 을 일반적으로 나타낸다.
그러나, Big-O 표기법에서 로그의 밑은 그다지 중요하지 않다. 즉, 점근 표기법에서 log의 밑은 의미에 크게 영향을 주지 않으므로 신경쓰지 않아도 된다.

void Logarithmic(n){
	i = 1; //1
    while(i<n){ //log2 n+1
    	printf(i); //log2 n
        i = i * 2; //log2 n
    }
}

while(i<n) 만 보면 n번 반복할 것 같지만, i=ix2로 인해 숫자는 1->2->4->8->16... 인 2의 거듭제곱으로 커지기 때문에 위 while문은 log2 n 만큼 반복된다.

1+log2 n+1+log2 n+log2 n = 3log2 n+2 => O(log n)

void Logarithmic(n){
	i = 1; //1
    while(i>1){ //log2 n+1
    	printf(i); //log2 n
        i = i / 2; //log2 n
    }
}

나눗셈도 마찬가지!

---

O(n log n)

void nlogn(n){
	for(int i=1;i<n;i++){ //n번 반복
    	j=1; //n
        while(j<n){ //log n+1
        	print(i,j); //log n
            j = j * 2;  //log n
        }
    }
}

for문과 while문이 중첩되어 while문은 log n에 곱하기 n번 한 만큼 반복될 것이다.
for문이 while내에 중첩되든, while문이 for문 내에 중첩되든 상관없이 반복횟수는 각각 반복문의 곱셈이다.

n+n+(n*(log n+1+log n+log n)) = 2n+3n log n+n = 3n + 3n log n => O(n log n)