시간복잡도 (Time Complexity)

출처 : 인프런 - 코딩테스트 [ ALL IN ONE ]

문제 상황: 공 5개 오름차순 정렬
해결 방법:
(1) 가장 작은 숫자를 찾아서 맨 앞에 놓는다
(2) 남은 공들에 대해서 (1) 방법 반복

이 때, 해결방법이 알고리즘

Running Time

프로그램 실행 시간

시간 복잡도

• 시간과 입력값 n의 함수 관계
• 최고차수만을 이용해 Big - O(접근표기법) 사용

---

제약 조건

시간복잡도(Big-O)에 데이터의 크기(n)을 넣어서 나온 값이 100,000,000(10^8)이 넘으면 시간 제한 초과할 가능성이 있다!

실행시간이 작으려면 시간복잡도가 작아야한다.
O(1) < O(n) < O(n^2) < O(n^3)

Step1. 문제 이해하기

문제에서 최대한 정보 많이 뽑기

!제한 조건 보는 법

코드 적용해보기

• O(n)

for i range(n)
    print("proc") # 이 함수의 실행시간이 너무 크면 안되는 경우도 있다.

a = [1,2,3,4,5,6, ... , n] # O(n)

• O(1)

a = 7
b = 34
print("hello")

input(n) # n이 커져도 상관 없음
for i in range(100):
    print(n)

• O(n^2)

n = 10 # N을 원하는 값으로 설정

for i in range(n):
    for j in range(n):
        print("hello")

• O(nm)

lst1 = [1,2,3,4]
lst2 = [3,4,5,6,7,8,10]
common = []

for i in range(len(lst1)):
    for j in range(len(lst2)):
        if lst1[i] == lst2[j]:
            common.append(lst1[i])

함수, 연산자, 메서드의 시간복잡도

• list

리스트에 in 연산자를 쓰는 경우

# 총 7개의 방이 존재한다고 가정
# visited는 지금까지 방문한 모든 방의 번호를 저장
visited = [0, 1, 3, 5] # 방문한 곳의 노드 번호를 넣기
if 3 in visited: # O(n) -> 4가 아니라 visited가 방문할때마다 늘어난다. O(n)
    print("room number 3 visited")

for node in visited:
    print(node)

아래 코드처럼 시간 복잡도를 개선 -> access O(1)

visited = [True, True, False, True, False, True, False]
# if visited[3] == True:
if visited[3]: # list에서 access하는게 O(1)
   print("room number 3 visited")

• hashtable

visited = {0: True, 1: True, 3: True, 5: True}
if 3 in visited: # O(1)
    print("room number 3 visited")

# hash set
visited = set() 
visited = {0, 1, 3, 5}
if 5 in visited: # O(1)
    print("room number 5 visited")

• sort() - O(nlogn)
• heappush() / heappop() - O(logn)
• deque

import time
from collections import deque

# Deque를 사용한 예제
def deque_example():
    dq = deque()
    start_time = time.time()
    
    # 맨 앞에 100000번 요소 추가
    for i in range(100000):
        dq.append(i)
    
    # 맨 앞에서 100000번 요소 제거
    for i in range(100000):
        dq.popleft()
    
    end_time = time.time()
    print(f"Deque 작업 시간: {end_time - start_time} 초")

# list를 사용한 예제
def list_example():
    lst = []
    start_time = time.time()
    
    # 맨 앞에 100000번 요소 추가
    for i in range(100000):
        dq.append(i)
    
    # 맨 앞에서 100000번 요소 제거
    for i in range(100000):
        del lst[0]
    
    end_time = time.time()
    print(f"Deque 작업 시간: {end_time - start_time} 초")

# 실행
deque_example() # Deque 작업 시간: 0.012186
list_example() # List 작업 시간 : 3.02875