시간복잡도 개념 정리

 

시간복잡도

-> 문제를 해결하는데 걸리는 시간과 입력의 함수 관계

 

시간복잡도는 주로 빅-오 표기법을 사용하여 나타내며, 이 빅-오 표기법은 계수와 낮은 차수의 항을 제외시키는 방법

예시로서, 만약 크기 n의 모든 입력에 대한 알고리즘에 필요한 시간이 최대 (어떤 n0보다 크지 않은 모든 n에 대하여) 5n3 + 3n의 식을 가진다면, 이 알고리즘의 점근적 시간 복잡도는 O(n3)

 

 

 

위와 같은 별찍기 문제 알고리즘의 시간복잡도는 아래와 같습니다.

시간복잡도 

O(n²)인 정렬 알고리즘으로 풀 수 있는 문제.(ex)삽입 정렬, 거품 정렬)

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

2750번: 수 정렬하기

삽입정렬로 푼 것

#수 정렬하기
#시간복잡도 O(n**2)인 버블정렬,삽입정렬 등으로 풀어보자


N = int(input())
numbers = []
for i in range(N):
    numbers.append(int(input()))


def insert_sort(x):
    for i in range(1,len(x)):
        j = i-1
        key = x[i]
        while x[j] > key and j >= 0:
            x[j+1]=x[j]
            j = j-1
            x[j+1] = key
    return x
numbers = insert_sort(numbers)
for i in numbers:
    print(i)

N = 5 일 때  (4*5)/2 만큼의 시간복잡도가 필요

 

 

참고

https://ko.wikipedia.org/wiki/%EC%8B%9C%EA%B0%84_%EB%B3%B5%EC%9E%A1%EB%8F%84

시간 복잡도 - 위키백과, 우리 모두의 백과사전