Big O vs Big $ \ Theta $ durante a entrevista de codificação

Question

quase toda vez que vejo um artigo sobre tempo ou complexidade espacial, as pessoas estão expressando a complexidade com o Big O, enquanto que deveria ser $ \ theta $ . Do livro "Cracking a entrevista de codificação":

.

"na indústria (e, portanto, em entrevistas), as pessoas parecem se fundir θ e

Answer 1

Aqui está uma resposta do Reddit que achei o mais útil:

.

Eu acho que eu diria, se alguém disser: "O que é o tipo de inserção?", Você quer dizer "é $ O (n ^ 2) $ .Claro que não é precisamente a mesma coisa dizendo que é " $ \ theta (n ^ 2) $ no pior caso", mas é uma convenção que todos entendem eDemora menos tempo para tirar as palavras da sua boca.

Answer 2

Eu acho que está bem.Apenas mostra o entrevistador que você realmente sabe qual é o significado real do Big-O e Theta.Apenas certifique-se de que é verdadeira (a $ \ ômega $ parte) quando você tem um algoritmo complicado e você usou alguma desigualdade para a prova de complexidade big-o.

Answer 3

Se você mencionar o Big-Theta, muitos entrevistadores pensarão que estão errados porque nunca ouviram falar disso.Se você começar a debater, então você falha no que a entrevista é principalmente sobre: convencendo o entrevistador que eles querem trabalhar com você.

Pergunta: Você verifica se X é um primo testando a divisibilidade em 2, 3, 5, 7, 11 etc. Qual é o Big-O da complexidade de tempo?Se você responder "é big-theta", qual será a minha opinião?