알고리즘 문제를 풀거나 알고리즘 문제를 풀다가 막혀서 다른 사람의 풀이를 볼 때 자주 들리는 단어들이 있을 것이다 그 중 우리는 오늘은 알고리즘 문제 풀이에서 중요한 개념인 ‘빅오 표현법’과 ‘시간 복잡도’에 대해 설명하려고 한다

빅오 표현법(Big O Notation)이란?

우선 빅오 표현법에 대해 먼저 알아보면 빅오 표현법이란 알고리즘의 효율성을 표현하는 방법 중 하나로 주로 알고리즘의 ‘최악의 경우’에 대한 실행 시간이나 필요한 메모리 공간을 나타내는 데 사용되는 표현법이다

기본적인 빅오 표현들을 살펴보면

이렇게 확인할 수 있다

시간 복잡도(Time Complexity)란?

다음으로 보통 빅오 표현법과 묶여서 설명되는 시간 복잡도에 대해서도 알아보면 시간 복잡도는 알고리즘이 문제를 해결하는데 걸리는 시간을 추정할 수 있는 방법으로 시간 복잡도를 통해 입력 크기가 커질 때 알고리즘의 실행 시간이 어떻게 변하는지 파악할 수 있어서

알고리즘 문제를 풀 때 시간 복잡도를 계산하여 시간 초과가 발생하는지 테스트 케이스를 거치지 않고도 미리 계산할 수 있기에 잘못된 알고리즘을 제출하거나 잘못된 알고리즘을 구현하느라 시간 낭비하는 일을 막을 수 있다

그렇다면 이러한 시간 복잡도는 어떻게 계산할 수 있을까? 시간 복잡도를 계산하는 방법은 생각보다 어렵지 않은데

이제 마지막으로 실제 예시를 통해 시간 복잡도를 구해보면

  
def sum_array(arr):
    total = 0
    for element in arr:
        total += element
    return total

위 코드는 배열 내의 모든 요소의 합을 구하는 알고리즘으로 해당 알고리즘에서는 배열의 각 요소를 한 번씩만 확인하므로 시간 복잡도는 O(N)이다

이렇게 빅오 표현법과 시간 복잡도에 대해서 알아봤는데 마지막으로 추가적인 팁을 주자면 대충 프로그래밍에서 1억번 연산이 1초이기 때문에 이를 이용하여 시간 제한을 구하면 편하다

밑은 1초까지 몇번 가능한지 나타낸 표이다