Эти вопросы возникли по заданию домашней работы. Я не понимаю, почему? Похоже, вы всегда хотели бы выбрать алгоритм, который дает лучшее время работы.Причины, по которым вы можете использовать алгоритм времени Θ (n log n) по алгоритму времени Θ (n) для той же задачи
Значения Big O и Big Theta подразумевают, что для произвольно больших входных размеров производительность имеет тенденцию к некоторому пределу. Например, функция 99999999n равна O (n), но функция (1/9999999999) n^2 равна O (n^2). Однако для любого ввода разумного размера (не бесконечно большого) функция O (n^2), вероятно, будет быстрее.
Другими словами, если вы можете сделать предположения о своих входных данных, есть случаи, когда более плохой алгоритм может работать лучше.
Пример реального мира из приведенной выше концепции сортирует - существуют некоторые алгоритмы, которые выполняют в O (n) время, если массив уже отсортирован (сортировка пузыря). Если вы знаете, что многие ваши массивы уже отсортированы, по этой причине вы можете использовать сортировку пузырьков по методу слияния.
Другой угловой случай, когда вы, возможно, захотите не использовать более эффективный по времени алгоритм, - это эффективность пространства. Возможно, вы программируете на встроенном устройстве с очень небольшой оперативной памятью. Вы предпочли бы использовать меньше памяти и тратить немного больше времени, чем быть максимально эффективными по времени.
Благодарим вас за этот подробный ответ. Делает большой смысл. Кроме того, если вы не возражаете ответить на продолжение, мой проф. сказал, что большую тету можно назвать «лучшим случаем наихудшего случая». Не могли бы вы объяснить это разными словами? Мое понимание заключается в том, что большая тета является нижней границей для наихудшего размера ввода. тем не менее, я просто разбираю вещи, которые слышал, и не знаю, что это значит. – mdm508
@ mdm508 Big O - наихудшая временная сложность, большая Omega - лучшая временная сложность. Большая тэта - это комбинация обоих - если что-то есть θ (n^2), это означает, что как в худшем случае, так и в лучшем случае она будет ограничена сверху и снизу функцией k (n^2), где n сколь угодно велико и k - любая константа. Это, я полагаю, поэтому ваш профессор назвал это «наихудшим случаем наилучшего случая». Если бы это помогло вам поддержать и принять ответ, будем очень благодарны. – nhouser9
@ mdm508 Не беспокойтесь - я надеюсь, что мое объяснение помогло в любом случае. – nhouser9