Eu encontrei algumas perguntas no geeksforgeeks.org que eu não consigo entender (# 1 e # 3). Eu estava esperando que alguém pudesse esclarecer as respostas para mim:
esclarecer se verdadeiro / válido ou falso
1.Time Complexidade do QuickSort é Θ (n ^ 2)
Eu respondi verdade, mas é falso, por quê? Se quicksort tem uma complexidade de tempo de O (n ^ 2) e sabemos que Θ (g (n)) = {f (n) onde c1 * g (n) <= f (n) <= c2 * g (n ) e n> = n0} então isso não prova que isso é verdade já que c2 * g (n) sendo o limite superior igual a f (n)?
2.Time Complexidade do QuickSort é O (n ^ 2) - true
3.Time complexidade de todos os algoritmos de computador pode ser escrito como Ω (1)
Isso é verdade, mas eu não entendo porqueisso é verdade. Um algoritmo de busca pode ter um limite inferior de Ω (1) supondo que encontramos o que procurávamos no primeiro elemento, mas como isso é verdade para TODOS os algoritmos de computador, como algoritmo de ordenação por inserção, onde o pior caso é O (n ^ 2 )
ligação: http://www.geeksforgeeks.org/analysis-of-algorithms-set-3asymptotic-notations/
Respostas:
3 para resposta № 1A complexidade temporal do QuickSort é Θ (n ^ 2) ---- Isto significa que para cada valor de n, o tempo gasto pelo algoritmo para produzir a saída é igual a uma função que é f (n) = n ^ 2.mas sabemos que isso não é verdade para a classificação rápida porque sabemos que para alguma entrada, o tempo de execução da classificação rápida pode ser igual a uma função que é g (n) = nlogn. por isso precisamos especificar se é pior, melhor ou média caso.É correto dizer "Pior complexidade do tempo do caso de quicksort é Θ (n ^ 2)".
"A complexidade temporal do QuickSort é O (n ^ 2)" --- isto significa que para cada valor de entrada de n, o tempo de execução do algoritmo é no máximo uma função que é f (n) = n ^ 2.Isto implica que existe alguma entrada, para a qual o algoritmo tem um tempo de execução que pode ser menor que f (n) = n ^ 2.sabemos que o melhor caso de complexidade de tempo de quicksort é g (n) = nlogn e g (n) < f (n). Como esta declaração cobre todos os casos, então a afirmação é verdadeira.
Da mesma forma, é correto dizer "A complexidade do tempo do quicksort é Ω (nlogn)", porque isso significa que o tempo de execução do algoritmo é finalmente nlogn e n ^ 2> nlogn.
"A complexidade temporal de todos os algoritmos de computador podeser escrito como Ω (1) "--- aqui 1 representa a função de tempo constante. A declaração acima implica: para executar quaisquer algoritmos de computador, precisamos de um tempo constante mínimo. o que é correto para todos os algoritmos de computador.
1 para resposta № 2
O pior cenário para o QuickSort é O(n^2). Mas você espera que ele seja executado O(n log n) Tempo. Portanto, o tempo de execução do algoritmo varia por caso e você não pode usar o símbolo theta para fornecer o tempo geral de execução do algoritmo.
E, claro, o limite inferior no tempo de execução de qualquer algoritmo é o tempo constante (Ω(1)). Ele não precisa atingir esse limite inferior, mas o algoritmo deve ser executado e deve ter pelo menos uma operação.