알고리즘 - Big-O

시간복잡도에 관해 포스팅 한다 한다 말씀만 드리고 이제야 글을 쓰게 됩니다! 꾸벅..

오늘은 시간복잡도 , Big-O 에 관해 살펴보겠습니다.

git : 예제소스

Big-O ?

Big-O 표기법은 알고리즘 성능을 수학적으로 표현한 표기법입니다.

알고리즘 성능은 얼마나 많이 쓰냐 ( 공간 ), 얼마나 걸리냐 ( 시간 )에 따라 결정됩니다. 그래서 Big - O 표기법으로 시간 복잡도 / 공간 복잡도를 표기합니다.

시간 복잡도는 입력값과 연산 수행 시간의 상관관계를 나타냅니다.

그럼 아래에서 한번은 봤을법한 시간 복잡도의 표기법을 보겠습니다.

O(1)

Big-O 표기법은 O( ) 안에 표기를 해줍니다!

해당 표기법은 앞으로 보나 뒤로 보나 옆으로 보나 1 입니다….

맞습니다 위에서 말씀드렸지만, 시간복잡도는 입력값에 따른 수행 시간을 포커싱을 둡니다.

코드로 보면 아래와 같은 예를 들 수 있겠네요

func isFirstZero(_ intArray: [Int]) -> Bool {
    return intArray[0] == 0 ? true : false
}

전달인자로 int 배열을 받으며, 첫 번째 인덱스 값을 확인하여 0인지 아닌지 판단하는 함수입니다.

시간복잡도는 어디에 포커싱을 둔다고했죠?!? 입력값에 따른 수행시간이므로

해당 함수는 크기가 1인 배열이든, 100인 배열이든, 1000인 배열이든 항상 같은 수행시간이 걸릴겁니다.

이를 Big-O 표기법은 1을 대표 상수로 써 O(1) 로 나타냅니다.

O(n)

O(n) 과 같은 표기법은 맞습니다! 역시 눈치가 빠르시군요!

전달인자에 따라 수행시간도 같은 비례로 증가하는 경우입니다.

func printArray(_ number: Int) {
    for i in number {
        print(i)
    }
}

이는 위와 다르게 전달인자 크기가 커지면 커질수록 수행시간도 같은 비율로 커지게 됩니다.

만약 크기가 1인 number는 10만큼 걸린다고 가정했을때, 2인 number는 20만큼 걸리게되죠..

수학적 그래프로 생각하면.. y = 10x 입니다! 하지만 빅오표기법에서는 추세를 보고싶기 때문에 y = 2x, y = 256x에서 상수는 모두 제거하며 모두 O(n) 으로 표기합니다.

O(n^2)

이제 느낌 오셨나요??

O(n^2) 아래와 같이 나타 낼 수 있습니다!

func printSquare(_ number: Int) {
    for i in 1...number {
        var line = ""
        for j in 1...number {
            line += "\(i * j) "
        }
        print(line)
    }
}

위 같은 경우 이중 for문으로 number에 따라 line += "\(i * j) " 횟수가 결정되며, O(n^2) 으로 나타 낼 수 있습니다.

O(n * m)

func printSquare(_ width: Int, _ height: Int) {
    for i in 1...height {
        var line = ""
        for j in 1...width {
            line += "\(i * j) "
        }
        print(line)
    }
}

위와 같은 경우 수행시간을 결정하는 입력 값이 두개이며, 위와 같이 나타낼 수 있습니다.

O(2^n)

O(2^n) 시간 복잡도를 띄는 알고리즘은 익숙한 피보나치 수열의 재귀 방식입니다.

func getFibonacciNumber(_ index: Int) -> Int {
    if(index == 1) {
        return 1
    }
    if(index == 0) {
        return 0
    }
    
    return getFibonacciNumber(index - 2) + getFibonacciNumber(index - 1)
}

F(0) = F(0)

F(1) = F(1)

F(2) = F(1) + F(0)

F(3) = F(1) + F(2)

……

위와 같이 index가 0, 1이 아닌 경우 index - 2, index - 1로 둘로 계속 나뉘기 때문에 2^n과 같은 시간 복잡도를 보입니다.

O(logn)

O(logn) 시간복잡도를 띄는 대표적인 알고리즘은 이진탐색입니다.

func binarySearchArray(_ number: Int, _ array: [Int], _ min: Int, _ max: Int) -> Int? {
    
    if(min > max) {
        return nil
    }
    var index = min + max / 2
    
    if(array[index] == number) {
        return index
    } else if (number < array[index]) {
        return binarySearchArray(number, array, min, index)
    } else {
        return binarySearchArray(number, array, index, max)
    }
}

print(binarySearchArray(1 , [1,2,3,4], 0, 3))

위와 같이 함수가 진행 될 수록 범위가 반씩 줄기 때문에 O(logn)과 같은 시간 복잡도를 보입니다.

뒤로 갈수록 대표적인 알고리즘만 보여드린 경향이 없지 않지만 ,,, 이해가 되셨나요?!?

추가적인 설명 및 문의, 잘못된 정보가 있으면 댓글 남겨주세요! 오늘도 고생하셨습니다.

정리

∙ Big- O 는 알고리즘 성능 판단 표기법이며, 시간복잡도는 인풋에 따른 수행시간을 표현한다.

∙ Big- O 표기법은 변화의 추세를 보기위함이며, 크게 영향을 미치지 않는 상수들의 제외하여 표기한다.

---

https://www.youtube.com/watch?v=6Iq5iMCVsXA

https://www.youtube.com/watch?v=VcCkPrGaKrs