Big O VS Big $ \ Theta $ во время кодирования интервью

Question

Почти каждый раз, когда я вижу статью о времени или пространственном сложности, люди выражают сложность с большим o, тогда как он должен быть $ \ THETA $ . Из книги «взломать кодирующее интервью»:

"в промышленности (и, следовательно, в интервью) люди, кажется, имеют слияние θ и

Answer 1

Вот ответ от Reddit, который я нашел самым полезным:

Я думаю, что я бы сказал, если кто-то говорит: «Что o от вставки?», Вы хотите сказать «это $ O (n ^ 2) $ ".Конечно, это не именно то же самое, что говорят, что это « $ \ theta (n ^ 2) $ в худшем случае", но это соглашение о том, что все понимают, иЭто займет меньше времени, чтобы излечить слова из рта.

Answer 2

Я думаю, что это нормально.Это просто показывает интервьюеру, который вы на самом деле знаете, каковы реальные значения Big-O и Theta.Просто убедитесь, что это на самом деле True (The $ \ Omega $ Часть), когда у вас есть сложный алгоритм, и вы использовали некоторое неравенство для доказательств сложности Big-O.

Answer 3

Если вы упомяните, что Big-Theta многие интервьюеры будут думать, что вы ошибаетесь, потому что они никогда не слышали об этом.Если вы тогда начните обсуждать его, то вы потерпите неудачу в том, что собеседование в первую очередь: убедительный интервьюер, который они хотят работать с вами.

Вопрос: Вы проверяете, является ли X Prime, тестируя делимость на 2, 3, 5, 7, 11 и т. Д. Что такое Big-O времени сложности?Если вы ответите «Это большая тета», что будет мое мнение о тебе?