[알고리즘(1)] 시간복잡도/공간복잡도

출처: flaticon

 

본격적인 알고리즘을 공부하기에 앞서

[시간복잡도/공간복잡도를 배워야하는 이유]

1. 모든 기업은 최대한 빨리 적은 비용으로 서비스를 제공하고자 한다.

2. 이를 위해 최대한 효율적으로 문제를 푸는 능력을 요구한다.

3. 효율적으로 문제를 푼다는 것은 시간복잡도/공간복잡도를 고려한다는 의미다.

 

(공간복잡도는 많이 고려하지 않기도 하고 시간복잡도와 비슷하므로

시간복잡도를 기준으로 작성하겠다.)

 

[시간복잡도란?]

입력값의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 걸리는 정도이다.

 

예를 들면, 밥 1인분을 만드는 데에 10분이 걸린다고 하자.

그럼 10인분은 100분, 100인분은 1000분, 1000인분은 10000분이 걸린다. 

그럼 실제로 급식 아주머니들은 하루에 166시간 분량 만큼 일해서 급식을 제공했을까? 아니다.

분명 양이 늘어도 만드는 시간은 더 효율적이고 적게 들었을 것이다. 

개발이라는 것이 이런 과정이다. 1인분 만들 땐 10분이 걸리더라도

100인분, 1000인분을 만들 땐 1시간으로 끝내도록 만들어야 하는 것이다.

 

[시간복잡도 표기법]

시간복잡도를 표현할 때 세 가지 방법이 있다.

• Big-O(빅-오) ⇒ 상한 점근
• Big-Ω(빅-오메가) ⇒ 하한 점근
• Big-θ(빅-세타) ⇒ 그 둘의 평균

보통 빅오(Big-O)표기법을 사용해서 나타낸다.

왜냐하면 빅오 표기법은 최악의 경우를 고려하므로,

프로그램이 실행되는 과정에서 소요되는 최악의 시간까지 고려할 수 있기 때문이다.

 

[Big-O 표기법 종류]

 

1. O(1)

 

O(1)는 일정한 복잡도(constant complexity)라고 하며,

입력값이 증가하더라도 시간이 늘어나지 않는다.

arr = [1, 2, 3, 4, 5]
print(arr)

 

2. O(logN)

 

O(log n)은 로그 복잡도(logarithmic complexity)라고 부르며,

Big-O표기법중 O(1) 다음으로 빠른 시간 복잡도를 가진다.

def binary_search(target, data):
    data.sort()
    start = 0 			# 맨 처음 위치
    end = len(data) - 1 	# 맨 마지막 위치

    while start <= end:
        mid = (start + end) // 2 # 중간값

        if data[mid] == target:
            return mid 		# target 위치 반환

        elif data[mid] > target: # target이 작으면 왼쪽을 더 탐색
            end = mid - 1
        else:                    # target이 크면 오른쪽을 더 탐색
            start = mid + 1
    return

 

3. O(N)

 

O(n)은 선형 복잡도(linear complexity)라고 부르며,

입력값이 증가함에 따라 시간 또한 같은 비율로 증가하는 것을 의미한다.

N = 10
for i in range(N):
	print(i)

 

4. O(NlogN)

 

O(n log n)은 선형 로그 복잡도(linear logarithmic complexity)라고 부르며,

O(log n)에 n만큼 더 곱한 시간만큼 증가하는 것을 의미한다.

for i in range(n):
	for j in range(1, n, 10):
    		prinf("hello")

 

 

5. O(N^2)

 

O(n2)은 2차 복잡도(quadratic complexity)라고 부르며,

입력값이 증가함에 따라 시간이 n의 제곱수의 비율로 증가하는 것을 의미한다.

for i in range(N):
	for j in range(N):
    		print(i, j)

 

6. O(2^N)

 

O(2n)은 기하급수적 복잡도(exponential complexity)라고 부르며,

Big-O 표기법 중 가장 느린 시간 복잡도를 가진다.

def fib(n):
    a,b = 1,1
    if n==1 or n==2:
        return 1
        
    for i in range(1,n):
        a,b = b, a+b

    return a

 

7. O(N!)

 

이 경우의 수는 거의 사용되지 않는 방법인데 위에 표시된 O(2^N)보다 

더 많은 시간이 걸리므로 지양되는 방법이다.

 

[덧붙임]

상수의 경우엔 빅오 표기법에서 생략된다.

왜냐면 빅오표기법은 실제 러닝타임을 재기 위한 도구가 아니라

장기적으로 데이터가 증가함에 따른 증가율을 예측하기 위한 것이기 때문이다.

 

 

참고링크

1. 블로그: https://hanamon.kr/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-time-complexity-%EC%8B%9C%EA%B0%84-%EB%B3%B5%EC%9E%A1%EB%8F%84/

2. 블로그: https://makemethink.tistory.com/110

3. 유튜브: https://www.youtube.com/watch?v=6Iq5iMCVsXA