Eu matematicamente entendo $ f (n) \ em O (g (n)) $: $ f (n) $ não crescer mais rápido do que $ g (n) $. Mais formalmente, $ \ exists c, n_0 $ s.t. $ f (n) \ leq cg (n) \ forall n \ geq n_0 $.
Da mesma forma, $ f (n) \ in \ Theta (g (n)) $ significa que $ f (n) $ cresce aproximadamente tão rápido quanto $ g (n) $. ou seja, $ f (n) \ em O (g (n)), \ Omega (g (n)) $.
O que eu não entendo é por que as pessoas usam grandes Oh para o tempo de execução de um algoritmo? Não deveríamos usar grande Theta. Quando dizemos “Tempo de execução” de um algoritmo, nos referimos ao pior caso de tempo de execução, ou seja, $ T (n) = max \ {ALG (x): | x | = n \} $.
Então, ex: o pior caso de tempo de execução de pesquisa linear em uma entrada de tamanho $ n $ ($ n $ elementos e um valor de destino) é $ \ Theta (n) $ e $ O (n) $, mas $ \ Theta (n) $ fornece mais informações. Então, por que os livros de algoritmos usam $ O (n) $ e não $ \ Theta (n) $.
Comentários
- Freqüentemente, ‘ s porque simplesmente não podemos ‘ obter um limite estreito de big-theta no tempo de execução de um algoritmo. Se um algoritmo for suficientemente complicado, pode acontecer que o melhor que podemos fazer é dizer que o tempo de execução é, digamos $ O (n ^ {n!}) $ Onde, na verdade, pode ser $ \ Theta (2 ^ {n \ log n \ log \ log n}) $.
- Razões históricas.
- ” O que eu não ‘ t get é por que as pessoas usam big Oh para o tempo de execução de um algoritmo? Não deveríamos ‘ usar o grande Theta. ” – Sim. Espere, não, devemos fazer declarações ainda mais precisas. Mas se eu tiver que escolher, sim, $ \ Theta $!
Resposta
Vejo duas razões para as pessoas preferem Big Oh em vez de Big Theta:
- A complexidade de tempo de execução de um algoritmo não necessariamente é definida como a complexidade de tempo de execução de pior caso. Você também pode vê-lo apenas como o tempo de execução em uma instância arbitrária de comprimento $ n $. Então, se você escrever por exemplo que o tempo de execução $ t (n) $ de um algoritmo está em $ \ mathcal {O} (n ^ 2) $, isso significa que qualquer entrada de comprimento $ n $ que você escolher, ela sempre aumentará assintoticamente mais lento do que a função $ c \ cdot n ^ 2 $ para alguma constante $ c $ – então, obviamente, estamos fazendo uma declaração sobre o pior caso de tempo de execução.
- Às vezes, quando você analisa o tempo de execução complexidade de um algoritmo que você não sabe ao certo se a complexidade do pior caso que você está fornecendo é realmente pequena. Veja, por exemplo, a complexidade de tempo de execução da multiplicação de matrizes . Ainda não está claro se o tempo de execução $ n ^ {2.3728639} $ é realmente o pior caso. E assim o tempo de execução é conhecido por estar em $ \ mathcal {O} (n ^ {2.3728639}) $ enquanto ele ” não tenho certeza se está em $ \ Theta (n ^ {2.3728639}) $.
Mas também, você está certo que, em alguns casos, seria melhor fornecer um Big Theta limite do que um limite de Big Oh.
Comentários
- Anúncio 1: Leitores, tenham cuidado não leia muito sobre isso !
Resposta
Um limite superior (desleixado) é mais fácil de provar do que um limite superior rígido, sem falar dos limites e inferiores superiores.
O tempo de execução de alguns algoritmos não pode ser ser fornecido com a mesma função do limite superior / inferior. Por exemplo. algoritmos de classificação simples são $ O (n ^ 2) $, mas têm limite inferior $ \ Omega (n) $.
Alguns insistem em se esforçar para fornecer desempenho em termos assintóticos por meio de $ \ sim $, onde $ f (n) \ sim g (n) $ if
$$ \ lim_ {n \ to \ infty} \ frac {f (n)} {g (n)} = 1 $$
(digamos como uma média, ou pior caso, em termos de número de alguma operação crítica, como comparações durante a classificação). Ou seja, espaço de manobra, mas nenhuma (possivelmente gigantesca) constante varrida para debaixo do tapete.
Comentários
- Quando nos referimos a ” runtime “, nos referimos a algo como tempo de execução de melhor caso, tempo de execução de pior caso e tempo de execução de caso médio. Por exemplo: Quicksort tem $ \ Theta (n ^ 2) $ tempo de execução do pior caso e $ \ Theta (n) $ tempo de execução do melhor caso. Os assintóticos são definidos nas funções certas.
Resposta
Se big-Theta pode ser usado no lugar de big- Oh, deve ser usado a menos que acrescente uma dificuldade desnecessária para o entendimento. Existem alguns casos sutis em que big-Theta não pode ser usado no lugar de big-Oh, por exemplo:
Considere o seguinte problema: classificar matrizes de comprimento uniforme. O programa para resolver este problema poderia ser: se o comprimento da matriz for ímpar, saia imediatamente, se o comprimento da matriz for par, faça a classificação por bolha. Qual é o pior caso de tempo de execução deste algoritmo?
Certamente é $ O (n ^ 2) $, mas NÃO é $ \ Omega (n ^ 2) $ no sentido $ \ Omega $ é geralmente definido. Em vez disso, seu pior caso de tempo de execução é “$ \ Omega (n ^ 2) $ infinitamente frequentemente”, por assim dizer (aviso: terminologia não padrão).
Resposta
Na resposta de “por que os livros de algoritmo usam big-Oh e não Theta”:
Big-Oh é usado para a análise do pior caso e Big-Omega é usado apenas para o melhor caso. Mas, analisando em termos de Big-Theta, falamos sobre Big-Oh & Big-Omega simultaneamente.
ie. Para Big-Theta é necessário que Big-Oh == Big-Omega, caso contrário não podemos falar em Big-Theta.
Então, onde quer que (livro / qualquer documento) você veja o uso de Big-Theta, eles estão fornecendo a complexidade de Big-Oh & Big-Omega (e ambos são iguais também). Mas muitos casos eles não são iguais, então usamos apenas Big- Oh, apenas para o pior caso.