Estou lendo este post no Big-O
. Diz que o seguinte código é O (n ^ 2):
bool ContainsDuplicates(String[] strings)
{
for(int i = 0; i < strings.Length; i++)
{
for(int j = 0; j < strings.Length; j++)
{
if(i == j) // Don't compare with self
{
continue;
}
if(strings[i] == strings[j])
{
return true;
}
}
}
return false;
}
Mas eu não consigo entender o porquê.
O loop interno faz algo constante.
Portanto, é somatório de 1 .... N de uma constante. ou seja, número constante O (1).
O loop externo é somatório sobre o O (1).
Então, eu imagino que seja n * O (1).
Acho que estou entendendo algo errado aqui.
Eu não acho que todos os loops aninhados significam O (n ^ 2), certo?
algorithms
performance
complexity
big-o
user10326
fonte
fonte
i+1vez de0. Como está escrito, na pior das hipóteses (sem bobagens) 1/2, as comparações são redundantes.O(N), esse código seriaO(N^2 * M)onde M é o comprimento das strings.Respostas:
Seu erro é com o loop interno. Faz algo constante n vezes, por isso é O ( n ). O loop externo executa o loop interno n vezes, então é O ( n × n ) ou O ( n 2 ).
Em geral, se o número de iterações que um loop faz depende do tamanho da entrada, é O ( n ). E se k tais loops estão aninhados, é O ( n k ).
fonte
ContainsDuplicatesfunção / método da pergunta provavelmente não será usada com cromossomos completos.Se o comprimento da string for
n, o teste ifi == jserá executado n ^ 2 vezes. A ordem de um algoritmo é a ordem de qualquer parte dele que tenha a ordem mais alta. Como 'i' é comparado a 'j' n ^ 2 vezes, a ordem do algoritmo não pode ser menor queO(n^2).Para um 'n' muito grande, dobrar 'n' quadruplicará o tempo de execução.
fonte
i==jum O (1)?Você está interpretando mal o que significa uma operação constante.
Uma operação constante é uma operação que sempre executa em uma quantidade fixa de tempo, independentemente da entrada que recebe.
i == j é uma operação constante porque executa esta instrução em um período fixo de tempo. Vamos dizer que leva 1 unidade de tempo.
Mas essa operação constante é realizada (não dos valores de i) * (não dos valores de j) vezes. Digamos que iej sejam executados 10 vezes cada. Então, pelo cálculo, leva 100 unidades de tempo para a conclusão de i == j quando em um loop aninhado. Portanto, variará conforme os valores de iej.
Podemos ter certeza de que i == j será executado em 1 unidade de tempo, mas não podemos saber quantas vezes i == j será executado.
Se for realizado n vezes, levará n unidades de tempo. O loop externo executa o loop interno n vezes. Então, em essência, i == j operações são feitas n ^ 2 vezes.
Todos os loops aninhados significam O (n ^ (nenhum dos loops aninhados)). Aqui O significa o limite superior, o que significa que o código será executado menor ou igual ao valor de O (). Esta é a garantia de que não levará mais tempo do que isso, mas pode demorar menos e não ser maior.
fonte
Loops aninhados executam O ( i 1 * i 2 * ... * i n ), onde n é o número de loops aninhados e i x é o número de iterações no loop x . (Ou, em outras palavras, é o produto do número de iterações em cada um dos loops.)
Seu par de loops itera duas vezes na mesma matriz, que por coincidência é O (n * n) ou O (n 2 ).
O que acontece dentro do loop mais interno é tratado como constante, porque sempre acontece. A notação Big-O não é realmente medir o desempenho do código linear, é mais fazer comparações relativas de como os algoritmos iterativos se comportam quando recebem n itens de entrada para lidar. Certas operações que na verdade não fazem iterações (como push ou pop em uma pilha) são tingidas como O (1) porque elas manipulam um elemento dos dados.
fonte