complexidade logarítmica representada com loop? - algoritmo, teoria da complexidade, big-o

Até onde eu entendi, complexidade linear pode ser representada como loop simples e complexidade quadrática pode ser representada como loop aninhado. Como a complexidade cúbica e logarítmica pode ser representada?

Obrigado!

Respostas:

Um loop simples pode ter complexidade logarítmica, e.

for (i = 1; i <= N; i *= 2)
...

Como outros já responderam, um loop aninhado triplo terá complexidade cúbica.

Como cubic é O (n ^ 3), seriam três loops aninhados.

Logarítmico não é tão simples e geralmenterequer uma relação recursiva. Por exemplo, MergeSort é O (n * log (n)) porque forma uma árvore de recursão de altura log (n) e cada nível requer uma operação de fusão O (n).

Complexidade cúbica - dois loops aninhados:

foreach
foreach
foreach
// actions
end
end
end

Exemplo de complexidade de logaritmo - pesquisa binária.

• Cubic - três loops aninhados
• Logarítmica - a ideia de que em cada ciclo de loopvocê está dividindo o conjunto de dados de entrada por partes (ou de alguma forma o torna menor) e, no próximo ciclo, encurta o conjunto de dados, de modo que basicamente a complexidade não cresce significativamente enquanto o crescimento dos dados de entrada é definido. Por exemplo, dê uma olhada no Algoritmo BinarySearch ou qualquer outro Dividir e conquistar algoritmo.

O (n ^ 3) pode ser representado por 3 loops aninhados.

O (log n) é representado por um loop, em que cada iteração, a quantidade de dados que precisam ser processados ​​é reduzida pela metade.