Big O VS Big $ \ theTa $ durante la entrevista de codificación

Question

Casi cada vez que veo un artículo sobre el tiempo o la complejidad del espacio, las personas están expresando la complejidad con BIG O, mientras que debe ser $ \ theTa $ . Desde el libro "Cracking the coding entrevista":

"En la industria (y, por lo tanto, en entrevistas), las personas parecen tener una combinación de θ y

Answer 1

Aquí hay una respuesta de REDDIT que encontré lo más útil:

Supongo que diría que, si alguien dice: "¿Qué es lo que es de inserción?", Quiere decir "Es $ O (n ^ 2) $ ".Seguro que no es precisamente lo mismo que decir que es " $ \ theta (n ^ 2) $ en el peor de los casos", pero es una convención que todos entienden, ySe necesita menos tiempo para sacar las palabras de su boca.

Answer 2

creo que está bien.Simplemente muestra al entrevistador que realmente sabe cuál es el verdadero significado de Big-O y Theta.Solo asegúrate de que sea realmente verdadero (el $ \ omega $ parte) cuando tiene un algoritmo complicado y ha utilizado cierta desigualdad para la prueba de complejidad de BIG-O.

Answer 3

Si mencionas a BIG-THETA, muchos entrevistadores pensarán que estás equivocado porque nunca se enteraron de eso.Si luego comienza a debatirlo, falla en lo que la entrevista se trata principalmente: convencer al entrevistador de que quieren trabajar con usted.

Pregunta: Usted verifica si X es un primo al probar la divisibilidad de 2, 3, 5, 7, 11, etc. ¿Cuál es el BIG-O de la complejidad del tiempo?Si respondes "Es BIG-THETA", ¿qué será mi opinión de usted?