시간 복잡도

백준 문제를 기반으로 시간 복잡도에 대한 개념을 정리해보자.

 

빅오 표기법

실행 시간을 표기할 때 빅오 표기법을 주로 사용한다.

수행 시간을 점근적 표기법 즉, n이 무한대로 늘어날 때 필요한 부분만 남기는 표기법으로 표현한 것이다.

상향선을 기준으로 표기하는 것으로 같은 말로 Worst case를 기준으로 실행 시간을 표현한 것이다.

 

다양한 표기법들이 존재하지만 주로 빅오 표기법을 사용하는 이유는 소프트웨어가 최악의 상황에서도 수행될 수 있는지를 확인할 수 있기 때문이다.

 

백준 24262번

MenOfPassion(A[], n) {
    i = ⌊n / 2⌋;
    return A[i]; # 코드1
}

 

우선 이 함수를 실행했을 때 실행 시간이 어느 정도일지를 표현하고 싶다.

실행 시간이란 함수/알고리즘 수행에 필요한 스텝의 수이다.

그리고 각 라인을 수행하기 위해 필요한 스텝 수는 상수라고 가정한다.

 

위의 함수는 n이 1이든 100이든 1000이든 n/2를 수행하여 해당하는 인덱스의 요소를 반환한다.

따라서 위의 함수는 상수 시간이 걸릴 것이다.

빅오 표기법으로 표현하면 O(1)이 된다.

 

따라서 코드의 수행 횟수는 n이 어떤 값이 되든 딱 한번만 수행하고, 최고차항의 차수는 0이 된다.

 

백준 24263

MenOfPassion(A[], n) {
    sum <- 0;
    for i <- 1 to n
        sum <- sum + A[i]; # 코드1
    return sum;
}

 

cost	times
c1	1
c2	n
c3	n
c4	1

 

각 라인을 수행하기 위한 스텝 수를 상수로 표현하고, 각각의 스텝을 진행할 때 걸리는 수행시간을 정리했다.

이를 통해 수행 시간을 다항식으로 나타낼 수 있다.

c1 * 1 + c2 * n + c3 * n + c4 * 1 = (c2 + c3) * n + c1 + c4

 

이때 점근적 표기법에 의해 최고차항만 의미가 있으므로 간단하게 빅오 표기법으로 O(N)으로 표현할 수 있다.

 

 

백준 24264번

MenOfPassion(A[], n) {
    sum <- 0;
    for i <- 1 to n
        for j <- 1 to n
            sum <- sum + A[i] × A[j]; # 코드1
    return sum;
}

 

cost	times
c1	1
c2	n
c3	n
c4	n*n
c5	1

 

i가 1부터 n까지 순회하는 것마다 j가 1부터 n까지 순회하고 있다. 

그렇기 때문에 수행 횟수는 n^2만큼 수행하게 되고, 수행시간은 O(N^2)으로 표현할 수 있다.

 

 

백준 24265번

MenOfPassion(A[], n) {
    sum <- 0;
    for i <- 1 to n - 1
        for j <- i + 1 to n
            sum <- sum + A[i] × A[j]; # 코드1
    return sum;
}

 

 

이 문제에서 알 수 있는 것은 수행 횟수를 점근적 표기법으로 표현한 것이 수행 시간이라는 것이다.

 

예를 들어 n이 7이면 코드1은 1부터 n-1까지의 합만큼 알고리즘을 수행하게 된다.

따라서 수행 횟수를 1부터 n-1까지의 합으로 구할 수 있다.

그리고 수행 시간은 수행 횟수로부터 O(N^2)으로 표현할 수 있다.

 

⬇ 수행 횟수를 구하는 함수

function solution(n) {
  let sum = 0;
  for (let i = 1; i <= n - 1; i + 1) {
    sum += i;
  }

  return sum;
}

 

 

 

백준 24266

MenOfPassion(A[], n) {
    sum <- 0;
    for i <- 1 to n
        for j <- 1 to n
            for k <- 1 to n
                sum <- sum + A[i] × A[j] × A[k]; # 코드1
    return sum;
}

 

이 코드는 i가 n번 순회할 때마다 j도 n번 순회하고 k도 n번 순회한다.

따라서 알고리즘 수행시간을 O(N^3)로 표현할 수 있고, 수행 횟수를 구하는 식 또한 N^3와 같다.

 

 

백준 24267

MenOfPassion(A[], n) {
    sum <- 0;
    for i <- 1 to n - 2
        for j <- i + 1 to n - 1
            for k <- j + 1 to n
                sum <- sum + A[i] × A[j] × A[k]; # 코드1
    return sum;
}

 

해당 코드의 실행 횟수를 시그마의 합으로 표현할 수 있다.

또는  1 부터 n까지의 숫자중 3가지를 뽑아 중복 없이, 크기 순으로 작성하는 경우의 수가 수행 횟수가 된다.

수학적인 사고가 필요하다.

 

nC3 = n! / (n-3)! * 3! = (n-2)(n-1)n / 6

 

따라서 위의 식이 수행 횟수를 구할 수 있는 식이 되고, 수행 시간은 O(N^3)으로 표현할 수 있다.