Notação Big O - Exemplos em PHP

Este repositório contém explicações e exemplos práticos sobre Big O Notation, que é usada para descrever a complexidade algorítmica de algoritmos e funções, em termos de tempo e espaço.

O que é Big O Notation?

Big O Notation é uma forma matemática de descrever o comportamento assintótico de funções, ou seja, como o tempo de execução ou o uso de memória de um algoritmo cresce à medida que o tamanho da entrada aumenta. Ela fornece uma maneira de classificar algoritmos com base na sua eficiência.

Principais Complexidades

• O(1): Complexidade constante
• O(log n): Complexidade logarítmica
• O(n): Complexidade linear
• O(n log n): Complexidade linear-logarítmica
• O(n²): Complexidade quadrática
• O(2^n): Complexidade exponencial

Como Usar

1. Navegue até a pasta examples.
2. Abra os arquivos de exemplo para entender como cada complexidade é implementada.

---

Exemplos de Big O Notation

1. O(1) - Complexidade Constante

A complexidade constante significa que a função executa em um tempo fixo, independentemente do tamanho da entrada.

Exemplo:

<?php
function acessoElemento($arr, $index) {
    return $arr[$index];
}

$arr = [1, 2, 3, 4, 5];
echo acessoElemento($arr, 3);
?>

2. O(log n) - Complexidade Logarítmica

A complexidade logarítmica é frequentemente associada a algoritmos que dividem a entrada em pedaços menores, como a busca binária.

Exemplo:

<?php
function buscaBinaria($arr, $valor) {
    $inicio = 0;
    $fim = count($arr) - 1;

    while ($inicio <= $fim) {
        $meio = intdiv($inicio + $fim, 2);
        if ($arr[$meio] == $valor) {
            return $meio;
        } elseif ($arr[$meio] < $valor) {
            $inicio = $meio + 1;
        } else {
            $fim = $meio - 1;
        }
    }

    return -1; // Não encontrado
}

$arr = [1, 3, 5, 7, 9, 11, 13, 15];
echo buscaBinaria($arr, 7);
?>

3. O(n) - Complexidade Linear

A complexidade linear significa que o tempo de execução cresce diretamente com o tamanho da entrada.

Exemplo:

<?php
function somaArray($arr) {
    $soma = 0;
    foreach ($arr as $valor) {
        $soma += $valor;
    }
    return $soma;
}

$arr = [1, 2, 3, 4, 5];
echo somaArray($arr);
?>

4. O(n log n) - Complexidade Linear-Logarítmica

A complexidade linear-logarítmica ocorre em algoritmos como a ordenação por mergesort ou quicksort.

Exemplo:

<?php
function quicksort($arr) {
    if (count($arr) < 2) {
        return $arr;
    }

    $pivo = $arr[0];
    $menor = [];
    $maior = [];

    for ($i = 1; $i < count($arr); $i++) {
        if ($arr[$i] < $pivo) {
            $menor[] = $arr[$i];
        } else {
            $maior[] = $arr[$i];
        }
    }

    return array_merge(quicksort($menor), [$pivo], quicksort($maior));
}

$arr = [5, 2, 9, 1, 5, 6];
print_r(quicksort($arr));
?>

5. O(n²) - Complexidade Quadrática

A complexidade quadrática é geralmente vista em algoritmos que possuem loops aninhados, como o bubble sort.

Exemplo:

<?php
function bubbleSort($arr) {
    $n = count($arr);
    for ($i = 0; $i < $n; $i++) {
        for ($j = 0; $j < $n - 1 - $i; $j++) {
            if ($arr[$j] > $arr[$j + 1]) {
                $temp = $arr[$j];
                $arr[$j] = $arr[$j + 1];
                $arr[$j + 1] = $temp;
            }
        }
    }
    return $arr;
}

$arr = [64, 34, 25, 12, 22, 11, 90];
print_r(bubbleSort($arr));
?>

6. O(2^n) - Complexidade Exponencial

A complexidade exponencial é frequentemente associada a problemas de força bruta, como o cálculo de números de Fibonacci recursivamente.

Exemplo:

<?php
function fibonacci($n) {
    if ($n <= 1) {
        return $n;
    }
    return fibonacci($n - 1) + fibonacci($n - 2);
}

echo fibonacci(10);
?>

---

Contribuições

Contribuições para melhorar o conteúdo e os exemplos são bem-vindas! Feel free to open issues or submit pull requests.