[알고리즘/파이썬] 시간복잡도 | 백준 2750번: 수 정렬하기

 

 

코딩 테스트에서의 시간복잡도

코딩 테스트에서는 빅-오(O(n))(최악의 케이스)을 기준으로 수행시간을 계산하는 것이 좋다.

 

시간복잡도 도출기준

• 상수는 계산에서 제외
• 가장 많이 중첩된 반복문 수행횟수가 기단복잡도의 기준

연산횟수가 N, 3N 등 이라도 상수를 무시하므로 둘 다 시간복잡도는 O(n)으로 동일하다.

그러나 이중중첩문의 N**2의 경우 시간복잡도는 변화없이 N**2으로 유지된다.

 

 

 

---

 

 

 

백준 2750번: 수 정렬하기

2750번: 수 정렬하기

 

반응형

문제

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.

출력

첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

해설

x = int(input())
num_list = []
for i in range(x):
    num_list.append(int(input()))
num_list1 = sorted(num_list)
for i in range(len(num_list)):
    print(num_list1[i])

 

제한시간이 2초이기때문에 4,000만 번이하의 연산횟수로 문제를 해결해야한다.

 

버블정렬의 시간복잡도=O(N**2)  -> 부적합 알고리즘

병합정렬의 시간복잡도=O(nlogn) -> 적합 알고리즘