Algorithms
Swift
IOS
Apple

Big O notation

Rubens Machion

3 min readJul 25, 2024

Big O notation ou simplesmente Big O é uma anotação matemática que avalia o comportamento limite de uma função com base em seus argumentos. Em outras palavras é uma forma de calcular o desempenho de um algoritmo baseado no tempo ou espaço utilizado. Isso na matemática é chamado de análise assintótica de algoritmos.

Exemplos Comuns de Notação Big O com Código Swift

O(1) — Tempo Constante: O tempo de execução não depende do tamanho da entrada.
Exemplo: acessar um elemento em um array por índice.

func accessFirstElement(arr: [Int]) -> Int? {
    return arr.first
}

2. O(log n) — Tempo Logarítmico: O tempo de execução cresce logaritmicamente com o tamanho da entrada.
Exemplo: busca binária.

func binarySearch(arr: [Int], target: Int) -> Bool {
    var left = 0
    var right = arr.count - 1
    while left <= right {
        let mid = (left + right) / 2
        if arr[mid] == target {
            return true
        } else if arr[mid] < target {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    return false
}

3. O(n) — Tempo Linear: O tempo de execução cresce linearmente com o tamanho da entrada.
Exemplo: percorrer um array.

func printElements(arr: [Int]) {
    for element in arr {
        print(element)
    }
}

4. O(n log n) — Tempo Linear-Logarítmico: Comumente visto em algoritmos de ordenação eficientes, como mergesort e heapsort.

func mergeSort(arr: [Int]) -> [Int] {
    guard arr.count > 1 else { return arr }
    let mid = arr.count / 2
    let leftArray = mergeSort(arr: Array(arr[0..<mid]))
    let rightArray = mergeSort(arr: Array(arr[mid..<arr.count]))
    return merge(left: leftArray, right: rightArray)
}

func merge(left: [Int], right: [Int]) -> [Int] {
    var leftIndex = 0
    var rightIndex = 0
    var orderedArray: [Int] = []

    while leftIndex < left.count && rightIndex < right.count {
        if left[leftIndex] < right[rightIndex] {
            orderedArray.append(left[leftIndex])
            leftIndex += 1
        } else if left[leftIndex] > right[rightIndex]) {
            orderedArray.append(right[rightIndex])
            rightIndex += 1
        } else {
            orderedArray.append(left[leftIndex])
            leftIndex += 1
            orderedArray.append(right[rightIndex])
            rightIndex += 1
        }
    }

    while leftIndex < left.count {
        orderedArray.append(left[leftIndex])
        leftIndex += 1
    }

    while rightIndex < right.count {
        orderedArray.append(right[rightIndex])
        rightIndex += 1
    }

    return orderedArray
}

5. O(n²) — Tempo Quadrático: O tempo de execução cresce quadraticamente com o tamanho da entrada.
Exemplo: ordenação por inserção.

func insertionSort(arr: [Int]) -> [Int] {
    var array = arr
    for i in 1..<array.count {
        var j = i
        while j > 0 && array[j] < array[j - 1] {
            array.swapAt(j, j - 1)
            j -= 1
        }
    }
    return array
}

7. O(n!) — Tempo Fatorial: O tempo de execução cresce fatorialmente com o tamanho da entrada. Exemplo: resolver o problema do Caixeiro Viajante usando força bruta.

let cities = [
    "A": [0, 10, 15, 20],
    "B": [10, 0, 35, 25],
    "C": [15, 35, 0, 30],
    "D": [20, 25, 30, 0]
]

func tsp(cities: [String: [Int]]) -> Int {
    let keys = Array(cities.keys)
    var visited = Array(repeating: false, count: keys.count)
    visited[0] = true
    return tspHelper(cities: cities, visited: &visited, currPos: 0, count: 1, cost: 0, ans: Int.max)
}

func tspHelper(cities: [String: [Int]], visited: inout [Bool], currPos: Int, count: Int, cost: Int, ans: Int) -> Int {
    if count == cities.count {
        return min(ans, cost + cities.values[currPos][0])
    }
    var ans = ans
    for i in 0..<cities.count {
        if !visited[i] {
            visited[i] = true
            ans = tspHelper(cities: cities, visited: &visited, currPos: i, count: count + 1, cost: cost + cities.values[currPos][i], ans: ans)
            visited[i] = false
        }
    }
    return ans
}

A notação Big O é uma ferramenta fundamental para entender e analisar a eficiência de algoritmos. Compreender a notação Big O permite que desenvolvedores escolham e otimizem algoritmos de maneira eficaz, levando em consideração o comportamento assintótico e o impacto no desempenho. No entanto, é importante lembrar que a notação Big O não pode ser usada como único critério no mundo real. Fatores como constantes ocultas, eficiência de implementação, uso de memória e características específicas do problema também devem ser considerados ao escolher o melhor algoritmo para uma aplicação prática. Utilizar a notação Big O em conjunto com outras considerações práticas garantirá soluções mais eficientes e escaláveis.