[Algorithm] 시간 복잡도

1. 시간복잡도란? 

간단한 정의는 알고리즘의 성능을 설명하는 것이다. 이를 위해 알고리즘을 수행하기 위해 프로세스가 수행해야하는 연산을 수치화한 것이라고 생각하면 된다. 

이 시간복잡도는 주로 빅-오 표기법을 사용해 나타낸다. 

 

2. 빅오 표기법

시간 복잡도는 빅-오(Big-O), 빅-오메가(Big-Ω), 빅-세타(Big-θ) 방법으로 표기한다. 위 세가지 표기법은 각가 최악, 최선, 중간의 경우에 대하여 나타내는 방법이다. 연산 횟수가 다항식으로 표현될 경우, 최고차항을 제외한 모든 항과 최고차항의 계수를 제외시켜 나타낸다.

이 중에서도 빅오 표기법이 가장 자주 사용된다. " 이 정도 시간까지 걸릴 수 있다." 를 고려해야 그에 맞는 대응이 가능하기 때문이다. 

 

3. 빅오 표기법의 종류

복잡도	1	10	100
O(1)	1	1	1
O(log N)	0	2	5
O(N)	1	10	100
O(N^2)	1	100	10000
O(2^N)	1	1024	126765..
O(N!)	1	3628800	화면에 표현할 수 없음

 

4. O(1) :  상수, 일정한 복잡도

일정한 복잡도라고 하며, 입력값이 증가하더라도 시간이 늘어나지 않는다. 

 

def print():
	print("hello world")
    
    
    
혹은

def algorithm(arr,index){
	return arr[index];
}

 

 

5. O(N) :  선형 복잡도

- 입력값이 증가함에 따라 시간 또한 같은 비율로 증가한다. 

 

def print(n):
	for item in n:
    	print(item)

 

* 만약 위 코드에서 n이 2n이 되더라도 시간 복잡도는 O(2n)으로 표현한다. 입력값이 커질수록 계수의 의미는 점점 퇴색되기 때문이다. 

 

 

6. O(N^2) :  2차 복잡도

- 입력값이 증가함에 따라 시간이 n의 제곱수의 비율로 증가한다. 

ex. 이중 반복문

 

def print(input):
	for n in input:
    	for m in input:
        	print(n,m)

 

* n^3와 n^5도 모두 O(n^2)로 표기한다. n이 커지면 커질수록 지수가 주는 영향력이 점점 퇴색되기 때문이다. 

 

7. O(log n):  로그 복잡도

- log(1) 다음으로 빠른 시간 복잡도를 가진다. 

- 입력 크기에 따라 처리 시간이 증가한다. 주로 정렬 알고리즘에서 많이 사용된다.

ex. 이진 검색

 

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 
        elif data[mid] < target:
            start = mid + 1
        else:
            end = mid -1

    return None

 

8. O(2^n):  기하급수적 복잡도 

- 빅오 표기법중 가장 느린 시간 복잡도를 가진다. 구현한 알고리즘의 시간 복잡도가 O(2n)이라면 다른 접근 방식을 고민해보는 것이 좋다. 

ex. 재귀로 구현하는 피보나치 수열 

function fibonacci(n) {
	if (n<=1){
    	return 1
    }
    
    return fibonacci (n-1) + fibonacci (n-2)
}

 

* 문제

https://www.acmicpc.net/problem/2869

 

코딩테스트에서 사용하는 알고리즘에서는 보통 컴퓨터가 1초당 1억번 정도 연산할 수 있다고 가정한다. 위 문제의 시간 제한은 0.25초이므로 최대 2,500만번의 연산을 할 수 있다 -> 반복문을 사용한다면 보장하기 어렵다. 

: O(1)의 시간 복잡도를 사용해서 풀어야한다. 

 

A, B, V = map(int,input().split())
answer=(V-B-1)//(A-B)+1
print(answer)

 

*map 함수? 

map(functoin, iterable): 첫 번째 매개변수로는 함수가 오고 두 번째 매개변수로는 반복 가능한 자료형(리스트, 튜플 등)이 온다. 

두 번째 인자로 들어온 반복 가능한 자료형 (리스트나 튜플)을 첫 번째 인자로 들어온 함수에 하나씩 집어넣어서 함수를 수행한다. 

위 예제에서는 input().split()으로 들어온 리스트를 정수형으로 바꿔주고 있다. 

 

* 답 해설:

O(1)의 시간 복잡도를 사용하기 때문에 식으로 답이 나온다는 것을 알고 접근해야한다.

1. 고려해야할 점은 마지막 날짜에는 내려오기 전에 도달할 수도 있다는 것이다. 어차피 내려오는 것은 고려하지 않아도 되기 때문에 최종 답에 1을 빼서 마지막날은 계산에서 제외할 수 있다. 

2. 또 고려해야할 점은 마지막날이 아닌 경우 몫을 이용해서 답을 구하는데, 나머지가 있는 경우와 없는 경우 답이 달라진다. (없는 경우 답보다 1이 더 커진다.) 이를 고려하여 나눠야하는 수에 1을 빼준다. (자연수의 나눗셈이기 때문에 무관하다.)

 

 

 

참고) https://blog.chulgil.me/algorithm/ 

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/