Algoritmo de análise Pergunta
https://stackoverflow.com/questions/1066660
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
NOTA:. Estou ultra-novato na análise de algoritmos portanto, não tome nenhuma das minhas afirmações como verdades absolutas, nada (ou tudo) que eu Estado poderia estar errado
Oi, eu estou lendo sobre análise de algoritmos e "Big-O-notação" e eu caí intrigado sobre algo.
Suponha que você está convidado a imprimir todas as permutações de uma matriz de char, para [a, b, c] seriam ab, ac, ba, bc, ca e cb.
Bem, uma maneira de fazer isso seria (em Java):
for(int i = 0; i < arr.length; i++)
for(int q = 0; q < arr.length; q++)
if(i != q)
System.out.println(arr[i] + " " + arr[q]);
Este algoritmo tem uma notação de O (n 2 ) se eu estou correto.
Eu pensei outra maneira de fazê-lo:
for(int i = 0; i < arr.length; i++)
for(int q = i+1; q < arr.length; q++)
{
System.out.println(arr[i] + " " + arr[q]);
System.out.println(arr[q] + " " + arr[i]);
}
Agora, este algoritmo é duas vezes mais rápido do que o original , mas a menos que eu estou errado, por big-O-notação é também um O ( 2 )
Isso é correto? Provavelmente não é tão Vou reformular: Onde estou errado ??
Solução
Você está correto. O-notação lhe dá uma idéia de como o algoritmo escalas, e não a velocidade absoluta. Se você adicionar mais possibilidades, ambas as soluções serão dimensionados da mesma forma, mas sempre será duas vezes mais rápido que o outro.
O (n) as operações podem também ser mais lento do que O (n ^ 2) as operações, para suficientemente pequeno 'n'. Imagine o seu O (n) o cálculo envolve tomar 5 raízes quadradas, e seu O (n ^ 2) solução é uma comparação simples. O O (n ^ 2) funcionamento será mais rápido para pequenos conjuntos de dados. Mas quando n = 1000, e você está fazendo 5000 raízes quadradas, mas 1000000 comparações, então a O (n) pode começar a olhar melhor.
Outras dicas
Eu acho que a maioria das pessoas concordam primeiro é O (n ^ 2). pistas exteriores de ansa n vezes e corre laço interno n vezes a cada tempo de ansa exterior é executado. Assim, o tempo de execução é O (n * n), O (n ^ 2).
O segundo é O (n ^ 2), porque as pistas exteriores de ansa n vezes. As espiras internas corre n-1 vezes. Em média para este algoritmo, loop é executado interiores n / 2 vezes para cada espira externa. de modo que o tempo de execução deste algoritmo é O (n * n / 2) => O (1/2 * n ^ 2) => O (n ^ 2).
notação Big-O não diz nada sobre a velocidade do algoritmo exceto para o quão rápido ele é relativo a si mesmo quando o tamanho das mudanças de entrada.
Um algoritmo poderia ser O (1) ainda levar um milhão de anos. Outro algoritmo poderia ser O (n ^ 2), mas ser mais rápido do que um (n) algoritmo O para pequenas n.
Algumas das respostas para esta questão pode ajudar com este aspecto da big-O notação. As respostas para esta questão também pode ser útil.
Ignorar o problema de chamar a sua saída do programa "permutação":
Big-O-notação omite coeficientes constantes. E 2 é um coeficiente constante.
Assim, não há nada de errado para os programas de duas vezes mais rápido do que o original para ter o mesmo O ()
Você está correto. Dois algoritmos são equivalentes em Big O notação se um deles tem uma quantidade constante de tempo mais ( "Um leva 5 minutos mais do que B"), ou um múltiplo ( "Uma leva de 5 vezes mais do que B") ou ambos ( "A leva 2 vezes B mais um extra de 30 milissegundos ") para todos os tamanhos de entrada.
Aqui está um exemplo que usa um algoritmo fundamentalmente diferentes para fazer um tipo semelhante de problema. Primeiro, a versão mais lenta, que se parece muito com seu exemplo original:
boolean arraysHaveAMatch = false;
for (int i = 0; i < arr1.length(); i++) {
for (int j = i; j < arr2.length(); j++) {
if (arr1[i] == arr2[j]) {
arraysHaveAMatch = true;
}
}
}
Isso tem O (n ^ 2) o comportamento, assim como o seu original (ele ainda usa o mesmo atalho que você descobriu de começar o índice j do índice i em vez da partir de 0). Ora aqui está uma abordagem diferente:
boolean arraysHaveAMatch = false;
Set set = new HashSet<Integer>();
for (int i = 0; i < arr1.length(); i++) {
set.add(arr1[i]);
}
for (int j = 0; j < arr2.length(); j++) {
if (set.contains(arr2[j])) {
arraysHaveAMatch = true;
}
}
Agora, se você tentar executar estes, provavelmente você vai descobrir que a primeira versão corre mais rápido. Pelo menos se você tentar com matrizes de comprimento 10. Porque a segunda versão tem de lidar com a criação do objeto HashSet e todas as suas estruturas de dados internas, e porque tem que calcular um código de hash para cada inteiro. No entanto, se você tentar isso com matrizes de comprimento 10.000.000 você vai encontrar uma história completamente diferente. A primeira versão tem a examinar sobre 50,000,000,000,000 pares de números (cerca de (N * N) / 2); a segunda versão tem de realizar cálculos função hash em cerca de 20 milhões números (cerca de 2 * N). Neste caso, você certamente quer a segunda versão !!
A idéia básica por trás do Big O cálculo é (1) é razoavelmente fácil de calcular (você não precisa se preocupar com detalhes como quão rápido o seu CPU é ou que tipo de cache L2 que tem), e (2) que se preocupa com os pequenos problemas ... eles são rápidos o suficiente de qualquer maneira: é os grandes problemas que vão matar você! Estes não são sempre o caso (por vezes, não importa que tipo de cache de que você tem, e às vezes não importa quão bem as coisas executar em pequenos conjuntos de dados), mas eles estão perto o suficiente para a verdadeira muitas vezes suficiente para Big O para ser útil.
Você está certo sobre os dois sendo big-O n ao quadrado, e você realmente provou que isso é verdade na sua pergunta quando você disse "Agora, este algoritmo é duas vezes mais rápido do que o original. " Duas vezes como meio rápido multiplicado por 1/2 que é uma constante, então, por definição, eles estão no mesmo conjunto big-O.
Uma maneira de pensar sobre o Big O é a de considerar o quão bem os diferentes algoritmos se sairia mesmo em circunstâncias muito injusto. Por exemplo, se um foi executado em um supercomputador realmente poderoso eo outro foi executado em um relógio de pulso. Se é possível escolher um N que é tão grande que mesmo que o algoritmo de pior está sendo executado em um supercomputador, o relógio de pulso ainda pode terminar em primeiro lugar, então eles têm diferentes complexidades Big S. Se, por outro lado, você pode ver que o supercomputador será sempre ganhar, independentemente de qual algoritmo que você escolheu ou o quão grande o seu N foi, em seguida, ambos os algoritmos devem, por definição, têm a mesma complexidade.
Em seus algoritmos, o algoritmo mais rápido foi apenas duas vezes tão rápido quanto o primeiro. Este não é o suficiente de uma vantagem para o relógio de pulso para bater o supercomputador, mesmo que N era muito alta, 1 milhão, 1trillion, ou até mesmo o número de Graham, o relógio de bolso nunca poderia bater o super computador com esse algoritmo. O mesmo seria verdade se os dois trocaram de algoritmos. Portanto ambos os algoritmos, por definição de Big O, tem a mesma complexidade.
Suponha que eu tinha um algoritmo para fazer a mesma coisa em O ( n ) tempo. Agora também acho que deu-lhe um leque de 10000 caracteres. Seus algoritmos tomaria n ^ 2 e (1/2) n ^ 2 tempo, que é 100.000.000 e 50.000.000. O meu algoritmo levaria 10.000. Claramente esse fator de 1/2 não está fazendo a diferença, uma vez que a minha é muito mais rápido. O n ^ 2 termo é dito dominar os termos menores, como n e 1/2, essencialmente tornando-os insignificantes.
A grande-oh notação expressar uma família de função, então dizer "essa coisa é O (n²)" significa nada
Este não é pedantismo, é a única, maneira correta de entender essas coisas.
O (f) = {g | existe x_0 e c tal que, para todos os x> x_0, g (x) <= f (x) * C}
Agora, suponha que você está contando os passos que o seu algoritmo, no pior dos casos , faz em termos do tamanho da entrada: chamar essa função f. Se f \ em O (n²), então você pode dizer que o seu algoritmo tem um pior caso de O (n²) (mas também O (n³) ou O (2 ^ n)). A falta de sentido das constantes seguir a partir da definição (ver que c?).
A melhor maneira de entender a notação Big-O é obter a compreensão matemática da ideia por trás da notação. Procure significado de dicionário da palavra "Asymptote"
A line which approaches nearer to some curve than assignable distance, but, though
infinitely extended, would never meet it.
Isso define o tempo máximo de execução (imaginário porque linha assíntota atende a curva no infinito), de modo que sempre que você estará sob esse tempo.
Com essa idéia, você pode querer saber, Big-O, Pequeno-O e ômega notação.
Tenha sempre em mente, Big O notação representa o cenário de "pior caso". No seu exemplo, o primeiro algoritmo tem um caso médio da espira externa completa * loop interno cheio, por isso, é N ^ 2 de curso. Porque o segundo caso tem um exemplo onde é espira externa quase completa * loop interno cheio, ele tem de ser englobados na mesma pilha de n ^ 2, uma vez que é o pior caso. De lá, ele só fica melhor, e sua média em comparação com a primeira função é muito menor. Independentemente disso, como n cresce, seu funções tempo cresce exponencialmente, e isso é tudo Big O realmente lhe diz. As curvas exponenciais podem variar muito, mas no final do dia, eles são todos do mesmo tipo.
