시간복잡도(Big-O표기법)

Big-O 표기법을 이해하기 전에..

'수행횟수' -> '수행시간' -> 'Big-O표기법'

'수행횟수'가 몇번이냐에 따라 '수행시간'이 몇인지 결정되고, 그 수행시간을 표기하는 방법이 'Big-O'표기법이다.

'수행횟수'는 연산을 몇 번 수행했는지를 의미하는데, 연산의 종류는 아래와 같다.

연산의 종류

대입연산(=배정, 복사연산) : a = b와 같이 a레지스터에 b의 값을 복사해서 대입하는 연산

산술연산 : +, -, *, /

비교연산 : >, >=, <, <=, ==, !=

논리연산 : AND, OR, NOT

비트연산 : bit-AND, bit-OR, bit-NOT, bit-XOR,<<, >>

algorithm arrayMax(A, n)
	input : n개의 정수를 저장한 배열 A
    output : A의 수 중에서 최대값
   	currentMax = A[0]
    for i = 1 to n-1 do
    	if currentMax < A[i]
        	currentMax = A[i]
    return currentMax

  위의 슈도코드에서 연산의 수행횟수를 세보면..

1️⃣ 네번째 줄에서 '='연산이 한 번 수행되었고,

2️⃣ 다섯번째 줄에서 for문이 n-1번 수행되었다.

3️⃣ 그런데, 여섯번째 줄에 if문이 몇 수행될지는 모르는 상태다.

※시간복잡도를 따질 때는 최악의 인풋이 들어오는 경우를 가정한다.(어떤 입력이 들어오는 경우든 최악의 경우와 같거나 빠를 것이므로)

4️⃣ 결국, if문이 전부 참이라서 currentMax에 계속해서 새로운 A[i]값이 대입되는 최악의 상황을 가정한다.

5️⃣ if문의 수행횟수는 for문의 수행횟수와 같아진다.

6️⃣ for문이 n-1번 돌고 if문도 n-1번 돌아서 for문과 if문의 연산횟수는 총 2n-2가 되는 것이다.

7️⃣ 여기에 네번째 줄에서 '='연산을 수행해준 것을 더하면 총 2n-1회의 연산을 수행한 꼴이 된다.

8️⃣ 2n-1이 최악의 입력을 받았을 때 연산을 수행한 횟수이자 수행시간이 된다.

9️⃣ 마지막으로 수행시간 함수 T(n) = 2n-1로 표기한다.

  이를 Big-O표기법으로 표기하면..

1️⃣ 2n-1에서 최고차항을 제외한 나머지 항을 제거한다

2️⃣ 최고차항을 제거했으니 2n만 남는다. 여기서 계수도 제거해준다.

3️⃣ 계수도 제거하니 n만 남는다.

4️⃣ 이를 O(n)이라고 표기한다.

 

 결국, Big-O표기법은 알고리즘의 연산을 수행하는 데 시간이 얼마나 걸리는지 알기 위해 필요한 것이고,

모든 인풋을 고려할 수는 없으므로 가장 연산횟수가 많아지는 최악의 인풋만 생각한 표기법이다.

 

 

출처 : youtube 신찬수 교수님