A complexidade de algoritmos é dado por uma função. Quando estamos tratando de problemas clássicos não recursivos, normalmente nos deparamos com polinômios.
TL;DR, a resposta do @Isac mostra de modo muito elegante os resultados necessários
TL;DR2, ótima resposta com ótimo rigor matemático sobre a pertinência de função à sua ordem de complexidade
Como dito no comentário, a notação grande O
define conjuntos. Então, quando falamos que n^2 + n = O(n^2)
, estamos dizendo que a função n^2 + n
pertence ao conjunto O(n^2)
. Quando dizemos que O(n^2) = O(n^3)
estamos dizendo que o conjunto O(n^2)
está contido em O(n^3)
; note que essa operação não é comutativa, pois não é a igualdade tradicional, então, apesar de O(n^2) = O(n^3)
ser verdade, O(n^3) = O(n^2)
é falso.
Ok, agora como definimos a pertinência de uma função a um conjunto descrito por notação grande O
? Fazendo uma divisão de função levando ao limite do infinito (literalmente, volto nesse ponto mais tarde).
Você deve ter percebido que a notação grande O
é sempre acompanhada de uma função, certo? Como O(n log n)
, O(n)
, O(n^2)
, O(e^n)
, O(n^3 + n)
. A função dentro do parênteses representa seu comportamento; não achei um nome formal, mas podemos chamar essa função de assinatura do conjunto. o nome para essa função é função limitante (informação cortesia do @LINQ).
Para determinar se uma função f(x)
pertence ao conjunto O(g(n))
, precisamos saber se f(x)
domina a função de assinatura função limitante do conjunto g(x)
; se f(x)
dominar g(x)
, então f(x)
não pertence a O(g(x))
, pertence ao seu conjunto complementar omega(g(x))
.
Notação omega
: na notação grande O
, definimos quais funções tem comportamento assintótico máximo igual à assinatura limitante do conjunto, na notação omega
, definimos quais funções tem comportamento assintótico mínimo igual à assinatura do conjunto; por exemplo, insertion sort funciona em omega(n)
(conjunto previamente ordenado ou pouco bagunçado) mas merge sort funciona em omega(n log n)
Notação theta
: se f(x) = O(g(x))
e f(x) = omega(g(x))
, então f(x) = theta(g(x))
; a notação theta
estabelece comportamentos assintóticos mínimo e máximo ao mesmo tempo; por exemplo, bubble sort sem otimização funciona em theta(n^2)
.
Então, agora precisamos definir a operação de dominação entre funções. Vou chamar essa função de domina(f, g)
, ele recebe duas funções e retorna um de três resultados possíveis:
dominada
se f
for dominada por g
;
co-dominantes
se não é possível definir quem domina quem;
dominante
se f
dominar g
.
A função domina(f,g)
é descrita assim:
Pronto, agora sabemos dizer definir quando uma função f(x)
pertence a um grupo O(g(x))
, mas isso ainda não é suficiente para provar se dado algoritmo executa nessa ordem de complexidade. Para saber isso, é necessário saber mais ou menos quantas operações serão necessárias fazer para o algoritmo funcionar.
Definir quantidades de operações depende da máquina que vai executar o algoritmo. Por exemplo, um x86 tem como uma operação unitária somar dois números de 16 bits n
e m
retornando outro número de 16 bits fazendo uma soma em O(1)
; uma máquina de Turing simples usando notação unária não consegue fazer a soma em um termo constante de operações, mas precisaria fazer O(n + m)
operações para concluir o processamento.
Então, sim, soma(n, m) = O(1)
em processadores x86 com n
e m
com tamanho fixo de 16 bits, mas soma(n, m) = O(n + m)
numa máquina de Turing. (Nota: na máquina de Turing, não estamos limitando os valores de n
nem de m
).
Normalmente, operações aritméticas básicas (como soma, multiplicação e divisão) com números palpáveis são feitas em bitagem fixa e consideramos elas com peso O(1)
.
Pequena demonstração informal: b
é constante, portanto O(1)
; n
é limitado por b
dígitos, tendo tamanho O(b)
; a soma usando números binários é feita analisando cada bit de n
e de m
uma única vez, junto a uma variável auxiliar, portanto a máquina de Turing vai passar por todos os bits apenas uma vez, logo O(tamanho(n) + tamanho(m))
; como o tamanho é limitado a O(b)
, O(tamanho(n) + tamanho(m)) = O(O(b) + O(b)) = O(b + b) = O(2b) = O(b) = O(1)
.
Em casos não recursivos (nem direta nem indiretamente), basta verificar os laços para saber quantas operações são feitas. Vamos analisar o seu caso:
function somaMatriz(matA, size)
let soma = 0;
for(let i = 0; i < size; i++) {
for(let j = 0; j < size; j++) {
soma += a[i][j];
}
}
return soma;
}
Podemos destrinchar essa função em duas e ter o mesmo comportamento assintótico:
function somaLinha(matA, size, i) {
let soma = 0;
for(let j = 0; j < size; j++) {
soma += a[i][j];
}
return soma;
}
function somaMatriz(matA, size) {
let soma = 0;
for(let i = 0; i < size; i++) {
soma += somaLinha(matA, size, i);
}
return soma;
}
Isso quer dizer que somaMatriz(matA,size)
vai fazer O(size*O(somaLinha(matA,size,i)) + 2)
operações; size * O(somaLinha(matA,size,i))
porque o laço externo se repete size
vezes (i
de [0,size)
é O(size)
) fazendo a operação somaLinha(matA,size,i)
cada vez. O 2
que aparece é devido ao retorno e a inicialização, porém sabemos que qualquer função crescente domina um valor constante, então esse 2
acaba saindo da assinatura.
Muito bem, para definir agora o custo de somaLinha(matA,size,i)
podemos dividir ela em duas partes (de modo análogo a o que acabamos de fazer com somaMatriz(matA, size)
):
function operador_soma(a, b) {
return a + b;
}
function somaLinha(matA, size, i) {
let soma = 0;
for(let j = 0; j < size; j++) {
soma = operador_soma(soma, a[i][j]);
}
return soma;
}
De modo análogo, somaLinha(matA, size, i)
vai fazer O(size)
operações de operador_soma
. operador_soma
é só uma simples soma de números razoáveis e de bitagem fixa, então executa em O(1)
. Portanto, somaLinha(matA, size, i) = O(size * operador_soma) = O(size * O(1)) = O(size)
.
Substituindo esse resultado no comportamento assintótico de somaMatriz
, temos que O(simaMatriz,matA,size) = O(size*O(somaLinha(matA,size,i)) + 2) = O(size*O(O(size)) + 2) = O(size * size) = O(size ^2)
.
Quando o laço não tem um tamanho muito 100% definido de maneira óbvia, a análise é um pouco mais complicada.
Tome como exemplo a função que faz a união entre dois conjuntos ordenados (baseada na função dessa resposta:
entrada:
A, conjunto ordenado de elementos do tipo E
B, conjunto ordenado de elementos do tipo E
cmp, função sinal que compara dois elementos de E
retorno:
C, conjunto de elementos do tipo E oriundo da união de A e B
começo
i <- 0 # índice para iterar em A
j <- 0 # índice para iterar em B
C <- []
ultimo_elemento_adicionado <- null
enquanto i < A.tamanho && j < B.tamanho:
s = cmp(A[i], B[j])
se s == '0':
# elementos são iguais, um deles como elemento candidato
candidato <- A[i]
i <- i + 1
j <- j + 1
senão, se s == '-':
# A[i] < B[j], então próxima comparação será com A[i + 1] e B[j]; A[i] agora é candidato
candidato <- A[i]
i <- i + 1
senão # caso trivial onde s == '+':
# A[i] > B[j], então próxima comparação será com A[i] e B[j + 1]; B[j] agora é candidato
candidato <- B[j]
j <- j + 1
# agora vamos ver se o candidato deve ser inserido em C: precisa ser distinto do último elemento adicionado, ou ser o primeiro elemento adicionado
se ultimo_elemento_adicionado != null && cmp(candidato, ultimo_elemento_adicionado) != '0':
ultimo_elemento_adicionado = candidato
C.push(candidato)
# caso i ou j extrapolem o tamanho de A ou B, respectivamente, não há mais comparações a se fazer
retorna C
fim
Considerando que as operações de cmp
são executadas em tempo constante O(1)
e que adicionar um elemento no final de um conjunto indexado também é feito em O(1)
.
A condição de parada é quando i
alcança o tamanho de A
ou quando j
alcança o tamanho de B
. Para iteração do laço, obtemos que i
ou j
(ou inclusivo) são incrementados. Isso significa que, para parar pela condição de i >= A.tamanho
, serão necessárias A.tamanho
operações de incremento em i
; enquanto isso, para parar pela condição de j >= B.tamanho
, serão necessárias B.tamanho
operações de incremento em j
. Como cada iteração eu garanto que haja pelo menos um incremento, o máximo de iterações feitas é (A.tamanho - 1) + (B.tamanho - 1) + 1
, portanto esse laço precisa de O(A.tamanho + B.tamanho)
operações para ser executado.
No caso do merge sort, temos uma função recursiva. Sua análise é ainda mais complicada, então não vou me preocupar no formalismo dela, mas em passar a ideia geral.
Revisando o merge sort:
mergeSort(E[] entradaDesordenada, E[] areaTrabalho, int ini, int end) {
if (end - ini <= 1) {
return;
}
int middle = (ini + end) / 2;
mergeSort(areaTrabalho, entradaDesordenada, ini, middle);
mergeSort(areaTrabalho, entradaDesordenada, middle, end);
merge(entradaDesordenada, areaTrabalho, ini, middle, end);
}
A ideia do merge
é juntar dois conjuntos ordenados em um terceiro conjunto ordenado. O grosso do algoritmo é muito parecido com o algoritmo da união que apresentei anteriormente, tendo inclusive o mesmo comportamento. Portanto, merge(A) = O(tamanho(A))
; se chamarmos tamanho(A) = n
, temos que a complexidade de merge = O(n)
.
Então, só falta definir quantas vezes merge
vai ser chamado. A recursão mergeSort
é feita de modo que, na chamada recursiva, apenas a metade dos elementos são passadas. Então, a profundidade de chamadas recursivas é log2(n)
; como log2(n) = log(n) * log2(10)
, podemos dizer que a profundidade é O(log n)
. Para cada nível de recursão, mergeSort
vai ser chamado duas vezes, cada chamada com n/2
elementos; então cada nível vai chamar merge
para n/2
elementos 2 vezes.
A ideia geral pode ser vista nesta imagem:
Note que em cada nível executamos diversas vezes o merge
(uma execução para cada nó da árvore). Ao todo, a quantidade de elementos passíveis de merge, em um mesmo nível de profundidade da recursão, é n
. Portanto, ao todo temos que vão ser feitas O(profundidade da recursão * n)
operações. Como a profundidade é O(log n)
, a quantidade de operações é O(n log n)
.
Qual a relevância disso na vida prática? Bem, fiz um experimento para responder a uma pergunta sobre performance de algoritmos de ordenação. Você pode verificar os resultados na resposta. A diferença entre um algoritmo de complexidade temporal O(n log n)
e O(n^2)
chega a ser duas ordens de grandeza no tempo total para uma entrada com n=100.000
O
representa conjuntos. Usamos sinal de igualdade por vicio. O correto seria dizern^2 + n pertence a O(n^2)
lim(n->inf, 5n2+3n)=lim(n->inf, n(5n+3))
3 é desprezável face a 5n portanto...=lim(n->inf, 5n2)=5*lim(n->inf, n2)
==> ...O(n2)<=>
de equivalente, mas saiu me assimk
(que na pergunta está indicado comom
) numa equação do tipoan^2+bn