Big O vs Big $ \ theta $ pendant l'entretien de codage

Question

Presque chaque fois que je vois un article sur le temps ou la complexité de l'espace, les gens expriment la complexité avec Big O, alors que cela devrait être $ \ theta $ . Du livre "craquer l'entretien de codage":

"dans l'industrie (et donc dans les interviews), les gens semblent avoir fusionné θ et

Answer 1

Voici une réponse de Reddit que j'ai trouvé le plus utile:

Je suppose que je dirais que si quelqu'un dit: "Qu'est-ce que l'insertion trit?", vous voulez dire "c'est $ O (n ^ 2) $ ".Bien sûr, ce n'est pas précisément la même chose que de dire que c'est " $ \ theta (n ^ 2) $ dans le pire des cas", mais c'est une convention que tout le monde comprend, maisIl faut moins de temps pour faire sortir les mots de votre bouche.

Answer 2

Je pense que c'est bien.Il montre juste l'intervieweur que vous savez réellement quelle est la vraie signification de Big-O et de Theta.Assurez-vous simplement que c'est vrai (la $ \ OMEGA $ partie) Lorsque vous avez un algorithme compliqué et que vous avez utilisé une certaine inégalité pour une preuve de complexité Big-O.

Answer 3

Si vous mentionnez Big-theta, de nombreux intervieweurs penseront que vous vous tromperez parce qu'ils n'en ont jamais entendu parler.Si vous commencez ensuite à le débattre, vous échouez à ce que l'entretien concerne principalement: Convaincre l'intervieweur qu'ils veulent travailler avec vous.

Question: Vous vérifiez si X est une prime en testant une divisibilité par 2, 3, 5, 7, 11, etc. Quel est le Big-O de la complexité de temps?Si vous répondez "c'est Big-theta", que sera mon opinion sur vous?