[알고리즘] 시간 복잡도 (Python)

 

Do it! 알고리즘 코딩테스트: 파이썬 편과 자료구조 과목 학습 후 정리한 포스팅 입니다.

 

시간 복잡도는 알고리즘 선택의 기준이 된다.

시간 복잡도는 주어진 문제를 해결하기 위한 연산 횟수를 말한다.

 

 

 

 

I) 대표적인 시간 복잡도 유형 

- 빅-오메가(Big - Ω) : 최선일 때의 연산횟수를 나타낸 표기법

- 빅-세타(Big - θ) : 보통일 때의 연산횟수를 나타낸 표기법

- 빅-오(Big - O) : 최악일 때의 연산횟수를 나타낸 표기법

 

🍀코딩 테스트에서는  빅-오(Big - O)를 기준으로 수행 시간을 계산해야 한다.

     응시자가 작성한 프로그램으로 다양한 테스트 케이스를 수행해 모든 케이스를 통과해야 합격으로 판단하기 때문이다.

 

그렇다면 빅-오(Big - O) 시간 복잡도에 대해 구체적으로 알아보자.

 

 

 

 

II) 빅-오(Big - O) 시간 복잡도

Big O notation is used to classify algorithms according to how their running time or space requirements 
grow as the input size grow, dealing with the worst case scenario.

빅-오(Big - O) 시간 복잡도는 실행 시간과 공간 요구 사항의 증가에 따라 알고리즘 분류에 사용되는 시간 복잡도이며 구하기 쉽고, 기능과 직접적으로 연결되어 많이 사용된다.

 

Let f(n) and g(n) be functions mapping positive integer to positive real numbers. 
We say that f(n) is O(g(n)) if there is a real constant c > 0 and an integer constant n0 ≥ 1 
such that 𝑓(𝑛) ≤ 𝑐𝑔(𝑛), for 𝑛 ≥ 𝑛0

n이 일정 수준(n0)을 넘어가면 그 이상의 어떤 n을 대입해도 cg(n)보다 작은 상수 c가 존재한다.

이때 f(n)의 빅-오(Big - O) 시간 복잡도는 g(n)이다.

 

이제 빅-오(Big - O) 시간 복잡도를 실제 코딩 테스트에서 어떻게 활용하는지 알아보자.

 

 

 

 

 

 

III) 코딩 테스트에서의 빅-오(Big - O) 시간 복잡도

백준 [2751번]을 살펴보며 코딩 테스트에서의 빅-오(Big - O) 시간 복잡도를 생각해보자.

2751번: 수 정렬하기 2

문제

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

입력

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

 

🍀파이썬에서 2,000만번~1억번의 연산을 1초의 수행 시간으로 예측할 수 있다.

따라서 시간 제한에 따라 우리에게 주어진 최대 연산은 약 4,000만번이다.

 

단어의 개수는 최악의 연산 상황인 1,000,000으로 고려해야 한다.

 

시험 상황에서 우리 머릿속에 떠오른 2개의 알고리즘의 시간 복잡도가 O(

), O(nlogn)이 있다고 가정하자.

우리는 어떤 알고리즘을 선택하여 문제를 풀어야 할까?

 

O( ) : (1,000,000)^2 = 1,000,000,000,000,000 > 40,000,000 -> 부적합 알고리즘

O(nlogn) : 1,000,000log(1,000,000) ≈ 20,000,000 < 40,000,000 -> 적합 알고리즘

따라서 우리는 O(nlogn)의 시간 복잡도를 가진 알고리즘을 사용하여 문제를 풀어야 한다.

 

이렇듯 코딩 테스트에서의 빅-오(Big - O) 시간 복잡도는 필수적으로 고려해야 할 요소이다.

자신이 작성한 코드의 시간 복잡도를 찾아낼 수 있다면 실제 코딩 테스트에서 시간 초과가 발생햇을 때 문제가 되는 코드를 수정할 수 있다.

 

 

 

 

 

 

IV) 빅-오(Big - O) 시간 복잡도 관련 정리 노트 (자료구조)

 

 

 

 

 

 

 

                                                    

 

<Summary>

- 시간 복잡도는 알고리즘 선택의 기준

- 자료구조 시간에 배운 Big-O 시간복잡도의 중요성

 

*유의사항

- 알고리즘 공부 중인 인공지능공학과 학부생이 정리해서 남긴 정리입니다.

- 정확하지 않거나, 틀린 점이 있다면 댓글로 알려주시면 감사하겠습니다.