[DataStructure] Big O

bromp โ€ข 2022년 11월 8일 PM 03:41 โ€ข 41 โ€ข 0
bromp Profile Image Level 7
0

๐Ÿ’ก Big O ํ‘œ๊ธฐ๋ฒ•

ํ•จ์ˆ˜์˜ ์ฆ๊ฐ ์ถ”์„ธ๋ฅผ ๋น„๊ตํ•˜๋Š” ์ ๊ทผ ํ‘œ๊ธฐ๋ฒ•์—์„œ ์ƒํ•œ์„ (์ตœ์•…์˜ ์ƒํ™ฉ)์„ ํ‘œํ˜„ํ•˜๋Š” ํ‘œ๊ธฐ๋ฒ•์ด๋‹ค. computer science์—์„œ๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜์˜ ์„ฑ๋Šฅ์„ ๋น„๊ตํ• ๋•Œ ์‚ฌ์šฉํ•ฉ๋‹ˆ๋‹ค.


๐Ÿ’ก Time Complexity: ์‹œ๊ฐ„๋ณต์žก๋„

์ž…๋ ฅ๋œ N์˜ ํฌ๊ธฐ์— ๋”ฐ๋ผ ์‹คํ–‰๋˜๋Š” ์กฐ์ž‘์˜ ์ˆ˜๋ฅผ ๋‚˜ํƒ€๋‚ธ๋‹ค.


Constant Time(์ƒ์ˆ˜ ์‹œ๊ฐ„) - O(1)

func constantTime(_ n: Int) -> Int {
    let result = n * n
    return result
}

loop๊ฐ€ ์—†๊ณ  ๋‹จ์ˆœํ•œ ๊ณ„์‚ฐ๊ฒฐ๊ณผ๋ฅผ return ํ•˜๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜ ์ž…๋‹ˆ๋‹ค.


Linear Time(์„ ํ˜• ์‹œ๊ฐ„) - O(n)

func linearTime(_ A: [Int]) -> Int {
    for i in 0..<A.count {
        if A[i] == 0 {
            return 0
        }
    }
    return 1
}

์•Œ๊ณ ๋ฆฌ์ฆ˜์˜ ์„ฑ๋Šฅ์ด ๋งค๊ฐœ๋ณ€์ˆ˜๋ฅผ ํ†ตํ•ด ์ „๋‹ฌ๋œ ๊ฐ’์˜ ํฌ๊ธฐ์— ์˜์กดํ•ฉ๋‹ˆ๋‹ค.
linear time์€ ์ˆ˜ํ–‰ ์‹œ๊ฐ„์˜ ๊ธธ์ด๊ฐ€ ์ž…๋ ฅ๊ฐ’์˜ ํฌ๊ธฐ์— ์ •๋น„๋ก€ํ•ฉ๋‹ˆ๋‹ค.


Logarithmic time(๋กœ๊ทธ ์‹œ๊ฐ„) - O(log n)

func logarithmicTime(_ N: Int) -> Int {
    var n = N
    var result = 0
    while n > 1 {
        n /= 2
        result += 1
    }
    return result
}

BST(Binary Search Trees)๊ฐ™์€ ๋น ๋ฅธ ์•Œ๊ณ ๋ฆฌ์ฆ˜๋“ค ์ž…๋‹ˆ๋‹ค. ๊ทธ๋“ค์€ ๊ฒฐ๊ณผ๋ฅผ ์ฐพ์„๋•Œ ๋งˆ๋‹ค ๊ฒฐ๊ณผ๋ฅผ ๋ฐ˜์œผ๋กœ ๋‚˜๋ˆ•๋‹ˆ๋‹ค. ์ด ๋ฐ˜์œผ๋กœ ๋‚˜๋ˆ„๋Š”๊ฒƒ์ด O(log n) ๋กœ๊ทธ ์‹œ๊ฐ„ ์•Œ๊ณ ๋ฆฌ์ฆ˜ ์ž…๋‹ˆ๋‹ค.


Quadratic Time(2์ฐจ ์‹œ๊ฐ„) - O(n^2)

func quadratic(_ n: Int) -> Int {
    var result = 0
    for i in 0..<n {
        for j in i..<n {
            result += 1
            print("\(i) \(j)")
        }
    }
    return result
}

2์ค‘ ๋ฃจํ”„๋ฅผ ์‚ฌ์šฉํ•˜๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜์—์„œ ์ฃผ๋กœ ๋ฐœ์ƒํ•ฉ๋‹ˆ๋‹ค. ์ •๋‹ต์„ ์–ป์„ ์ˆ˜๋Š” ์žˆ์ง€๋งŒ ์†๋„๊ฐ€ ๋Š๋ฆฝ๋‹ˆ๋‹ค.


๐Ÿ’ก Space Complexity(๊ณต๊ฐ„ ๋ณต์žก๋„)

์•Œ๊ณ ๋ฆฌ์ฆ˜์ด ์‹คํ–‰๋  ๋•Œ ์‚ฌ์šฉํ•˜๋Š” ๋ฉ”๋ชจ๋ฆฌ์˜ ์–‘์„ ๋‚˜ํƒ€๋‚ธ๋‹ค.

์ผ๋ฐ˜์ ์œผ๋กœ Big O๋Š” ์‹œ๊ฐ„ ๋ณต์žก๋„๋ฅผ ๋งํ•ฉ๋‹ˆ๋‹ค. ๊ณต๊ฐ„ ๋ณต์žก๋„๋Š” ๋ณ€์ˆ˜๊ฐ€ ์–ผ๋งˆ๋‚˜ ์„ ์–ธ๋๋Š”์ง€ ๊ทธ๋ฆฌ๊ณ  ๋ณ€์ˆ˜๋“ค๊ณผ ๊ด€๋ จ๋œ cost์™€ ๊ด€๋ จ์žˆ์Šต๋‹ˆ๋‹ค.


๐Ÿ’ก Trading off space of time

๋‘ ๋ฐฐ์—ด์˜ ๊ณตํ†ต ์›์†Œ๊ฐ€ ์žˆ๋Š”์ง€ ์ฐพ๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ๋‹ค์Œ๊ณผ ๊ฐ™์ด 2๊ฐ€์ง€๋กœ ํ‘œํ˜„ํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.


๊ณต๊ฐ„๋ณต์žก๋„ ๊ด€์ ์—์„œ๋Š” ๋งค์šฐ ํšจ๊ณผ์ ์ด์ง€๋งŒ ์‹œ๊ฐ„๋ณต์žก๋Š” O(n^2)์œผ๋กœ ํฐํŽธ์ž…๋‹ˆ๋‹ค.

// Naive brute force O(n^2)
func commonItemsBrute(_ A: [Int], _ B: [Int]) -> Bool {
    for i in 0..<A.count {
        for j in 0..<B.count {
            if A[i] == B[j] {
                return true
            }
        }
    }
    return false
}
commonItemsBrute([1, 2, 3], [4, 5, 6])
commonItemsBrute([1, 2, 3], [3, 5, 6])

space๋ฅผ ์‚ฌ์šฉํ•ด์„œ Hash Map ๋ฐฉ๋ฒ•์„ ์‚ฌ์šฉํ•˜๋ฉด ์‹œ๊ฐ„๋ณต์žก๋„๋ฅผ ์ค„์ผ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

// Convert to hash and lookup via other index
func commonItemsHash(_ A: [Int], _ B: [Int]) -> Bool {
    
    // Still looping...but not nested - O(2n) vs O(n^2)
    var hashA = [Int: Bool]()
    for a in A { // O(n)
        hashA[a] = true
    }
    
    // Now lookup in the hash to see if elements of B exist
    for b in B {
        if hashA[b] == true {
            return true
        }
    }
    return false
}
commonItemsHash([1, 2, 3], [4, 5, 6])
commonItemsHash([1, 2, 3], [3, 5, 6])

์˜ˆ์‹œ์—์„œ์ฒ˜๋Ÿผ ์ €์žฅ ๊ณต๊ฐ„์ด ๋ถ€์กฑํ•œ ๊ฒฝ์šฐ์—๋Š” ์‹œ๊ฐ„ ๋ณต์žก๋„๋ฅผ ๋Š˜๋ ค์„œ ํ•ด๊ฒฐํ•˜๊ณ  ์ €์žฅ ๊ณต๊ฐ„์„ ํ™œ์šฉํ•  ์ˆ˜ ์žˆ๋Š” ๊ฒฝ์šฐ์—๋Š” ์ €์žฅ ๊ณต๊ฐ„์„ ์‚ฌ์šฉํ•ด์„œ ์‹œ๊ฐ„ ๋ณต์žก๋„๋ฅผ ์ค„์ผ ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

๋Œ“๊ธ€