Como f(n) < cg(n) especificar o tempo?

Question

Estive lendo este tutorial no tempo de complexidade, e eu estou um pouco confuso sobre a sua explicação do big $O$ notação.Ele escreve:

$O(g(n)) = $ { $f(n)$ :existem constantes positivas $c$ e $n_0$ de tal forma que R $0 \leq f(n) \leq c*g(n)$ para todos $n > n_0$.

A maneira como eu a entendo, $c*g(n)$ denota $c$ multiplicado por $g(n)$.Se este for o caso, então como é que a expressão acima especificar o tempo, e não apenas o que $c*g(n)$ é maior do que $f(n)$?Ou eu estou errado, e isso é um pouco de notação eu não entendo?Minha compreensão da complexidade de tempo é muito rudimentar, então me perdoe se isso é apenas um erro estúpido da minha parte.

Answer 1

Como f(n) < cg(n) especificar o tempo?

Não.Bachmann-Landau notação é simplesmente uma maneira útil para comparar o crescimento da taxa de funções.Ela não diz nada sobre o que essas funções médio, e podemos ter certeza de que Bachmann não estava pensando sobre computadores, quando ele veio com ele, em 1894.

Que significado você atribui a essas funções é até você.Por exemplo, quando da análise de comparação baseado em algoritmos de classificação, que normalmente levam $n$ para ser o número de elementos na coleção, e $f(n)$ para o número de comparações, ou o número de trocas, ou o número de comparações e de swaps.

Note, também, que tudo isso é sempre relativo a um modelo de máquina ou de um modelo de custo.

Como um exemplo muito simples, se eu pedisse a você que é o de algoritmos de pior caso passo a complexidade para copiar uma lista, você diria $S(n)$.Mas, na verdade, o resposta correta seria "eu não posso dizer que porque você não especificou o modelo de máquina".Porque, por exemplo, em uma máquina de Turing, a cópia de uma lista é $O(n^2)$, porque para cada elemento que está sendo copiado, a cabeça do TM tem a unidade mais e mais e mais para alcançar o final da lista para gravar o próximo elemento.

Answer 2

Dizendo que o tempo de execução de um algoritmo é, em $O(g(n))$ dá, como você observou, apenas um limite superior.Além disso, o limite superior é dado com as constantes $c$ e $n_0$ desconhecida.Então, sim, é um tanto fraco informações sobre o tempo de execução.

A constante não especificado $c$ pode conter informações sobre o custo real das operações básicas do algoritmo, que pode ser desconhecido e/ou variável entre as execuções, mas ainda custo de uma quantidade de tempo que é limitado.A constante não especificado $n_0$ reflete que o limite dado refere-se a grandes tamanhos de entrada (ou qualquer que seja o parâmetro $n$ está representando).

Outros símbolos são utilizados para dar a outros tipos ou informações mais precisas sobre o tempo de execução.