[시간 복잡도] 빅오 표기법 (Big-O)

Better <-------------------------------------------------> Worse

         O(1) ,   O(log n),     O(n),       O(n^2),   O(n^3),   O(2^n)

                             상수,         로그,    직선(선형),      선형로그,      제곱,       지수

---

요새 기술이 발전해서,

공간 복잡도보다는 시간복잡도가 훨 중요하다!

 

그래서, 시간을 최소화하여

효율적으로 코드를 작성해야 좋은 코드라고 할 수 있다고 한다.

 

(알고리즘은 무엇을 만들기 위한 일련의 과정)

 

 

시간 복잡도에서 가장 중요한 것은?

정해진 표현식에 가장 큰 영향을 미치는 n의 단위이다.

O(n) <- 괄호 안에 있는 n

 

 

---

시간 복잡도 구하는 방법

1. 최고차항을 찾는다.

2. 계수를 제거한다.

 

or

모든 횟수를 다 더한 뒤,

최고차항을 찾고, 계수를 제거하면 끝

apple=0 # 1
for i in range(n): 
	for j in range(n):
    	print("hello") # n*n
    print("world") # n

n^2+n+1

최고차항 : n^2

계수는 1이므로 제거할 게 없음

 

따라서 위 코드의 빅오는 O(n^2)

 

 

ex1)

int a = 0, b = 0; #1

for (i = 1; i < N; i++) {
    a = a + rand(); # n-1
}

for (j = 2; j < M; j++) {
    b = b + rand(); # m-2
}

N+M-2

> 최고차항만 가져오기 O(N+M)

 

 

ex2)

int a = 0; #1
for (i = 0; i < N; i++) { # N
    for (j = N; j > i; j--) { # N-i
        a = a + i + j;
    }
}

'''
i=0 , j=N~2 (i+2)
i=1, j=N~3 (i+2)
'''

1+ N*(N-i) = N*N + N-i+1

i는 상수니까,

최고차항은 N*N

 

O(N^2)

ex3)

점근적으로 효과적이다 = 입력 크기가 클 경우 빠르다.

 

---

O(logN) > 지금 밑지수에 2가 생략되어 있음!

자료의 개수가 2^n개라면?

이진 트리를 사용할 경우 

탐색의 수는 2분의 1씩 줄어든다.

이때, 이진 트리는 자식 노드가 2개!

 

자식 노드 : M개, 자료의 전체 개수 : N

---

O(nlogn)

: Quick sort, Merge sort, Heap sort

 

분할 (logn), 합병(n개 비교)

---

참고 출처

https://github.com/zeroam/studynote/blob/master/content/%5B%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98%5D%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98%EA%B3%BC-%EC%8B%9C%EA%B0%84%EB%B3%B5%EC%9E%A1%EB%8F%84.md

zeroam/studynote

https://dingrr.com/blog/post/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%8B%9C%EA%B0%84%EB%B3%B5%EC%9E%A1%EB%8F%84-%EC%98%88%EC%A0%9C-15%EC%A2%85

[알고리즘] 시간복잡도 예제 15종 | 블로그 | 딩그르르