코테 시간복잡도 정복하기 (빅오 cheat sheet)

https://github.com/jwasham/coding-interview-university?tab=readme-ov-file#algorithmic-complexity--big-o--asymptotic-analysis

GitHub - jwasham/coding-interview-university: A complete computer science study plan to become a software engineer.

코딩테스트에 관한 개요, 전반적으로 참고하기 좋은 글

빅오 표기법 cheat sheet 한장에 정리

 

 

 

 

빅오표기법이란?

최악의 상황을 가정하고 코드 실행에 걸리는 시간을 표기한 것

즉, 최악일 때(worst case)의 연산 횟수를 나타낸 표기법

 

코딩 테스트에서는 빅-오 표기법(O(n))을 기준으로 수행 시간을 계산하는 것이 좋습니다. 실제 테스트에서는 1개의 테스트 케이스로 합격, 불합격을 결정하지 않습니다. 응시자가 작성한 프로그램으로 다양한 테스트 케이스를 수행해 모든 케이스를 통과해야만 합격으로 판단 하므로 시간 복잡도를 판단할 때는 최악일 때 worst case 를 염두에 둬야 합니다.

다음은 빅-오 표기법(O(n))으로 표현한 시간 복잡도 그래프입니다. 각각의 시간 복잡도는 데이터 크기(N)의 증가에 따라 성능(수행 시간)이 다르다는 것을 확인할 수 있습니다.

 

 

복잡도는 항상 최악일 때, 즉 데이터의 크기가 가장 클 때를 기준으로 합니다.

 

연산 횟수 계산 방법

•연산 횟수 = 알고리즘 시간 복잡도 n값에 데이터의 최대 크기를 대입하여 도출

 

위 공식을 대입해 각 알고리즘이 이 문제에 적합한지 판단해 보겠습니다.

알고리즘 적합성 평가

•버블 정렬 = (1,000,000) 2 = 1,000,000,000,000 > 40,000,000 → 부적합 알고리즘

•병합 정렬 = 1,000,000log 2 (1,000,000) = 약 20,000,000 < 40,000,000 → 적합 알고리즘

문제에 주어진 시간 제한이 2초이므로 연산 횟수 4,000만 번 안에 원하는 답을 구해야 합니다.

버블 정렬은 약 1조 번의 연산 횟수가 필요하므로 이 문제를 풀기에 적합한 알고리즘이 아니라고 판단할 수 있습니다.

병합 정렬은 약 2,000만 번의 연산 횟수로 답을 구할 수 있으므로 문제를 풀기에 적합한 알고리즘이라고 판단할 수 있습니다.

 

이와 같이 시간 복잡도 분석으로 문제에서 사용할 수 있는 알고리즘을 선택할 수 있고, 이 범위를 바탕으로 문제의 실마리를 찾을 수 있습니다. 즉, 데이터의 크기(N)를 단서로 사용해야 하는 알고리즘을 추측해 볼 수 있습니다.

 

시간 복잡도를 바탕으로 코드 로직 개선하기

시간 복잡도는 작성한 코드의 비효율적인 로직 logic 을 개선하는 바탕으로도 사용할 수 있습니 다. 이 부분을 활용하려면 가장 먼저 코드의 시간 복잡도를 도출할 수 있어야 합니다. 시간 복잡도를 도출하려면 다음 2가지 기준을 고려해야 합니다.

시간 복잡도 도출 기준

① 상수는 시간 복잡도 계산에서 제외한다.

② 가장 많이 중첩된 반복문의 수행 횟수가 시간 복잡도의 기준이 된다

 

합 배열 S 정의

S[i] = A[0] + A[1] + A[2] + … + A[i-1] + A[i] # A[0]부터 A[i]까지의 합

합 배열은 기존의 리스트 데이터를 전처리한 배열이라 생각하면 됩니다. 이렇게 합 배열을 미리 구해 놓으면 기존 리스트의 일정 범위의 합을 구하는 시간 복잡도가 O(N)에서 O(1)로 감소합니다. 다음 그림을 통해 합 배열을 좀 더 자세히 설명해 보겠습니다.

인덱스

리스트 A 

합 배열 S

0 1 2 3 4 5

15 13 10 7 3 12

15 28 38 45 48 60

 

 

합 배열

A[i]부터 A[j]까지의 리스트 합을 합 배열 없이 구하는 경우, 최악의 경우는 i가 0이고 j가 N인 경우로 시간 복잡도는 O(N)입니다. 이런 경우 앞에서 알아본 합 배열을 사용하면 O(1) 안에 답을 구할 수 있습니다. 합 배열은 다음과 같은 간단한 공식으로 만들 수 있습니다.

합 배열 S를 만드는 공식

S[i] = S[i-1] + A[i]

 

 

출처

 

https://www.bigocheatsheet.com/

Big-O Algorithm Complexity Cheat Sheet (Know Thy Complexities!) @ericdrowell

 

시간복잡도 한번에 정리해둔 사이트