С множеством различных вариантов сортировки алгоритмов, всегда ли целесообразно использовать алгоритм более высокой сложности в любом примере?Когда оправдано использование алгоритма O (2^n)?
Единственная причина, по которой я могу думать, - это иметь очень короткий массив или массив, который был очень близок к сортировке или содержал только несколько разных чисел.
С множеством различных вариантов алгоритмов сортировки всегда ли целесообразно использовать алгоритм более высокой сложности в любом примере?
Это может быть, если сложность большого-O беспокойства является худшим случаем вы уверены, что не ударит, или n известен маленькими, как вы говорите (например, п является числом белых пешек слева на шахматной доске), а постоянные факторы более важны.
O (2^n) является экстремальным, хотя ... вы также должны учитывать стабильность своих причин для его использования - может ли кто-то (включая вас в будущем) случайно изменить код, лишающий пригодности O (2^n) и оставляя приложение блокироваться иногда, когда оно вызывается, а n выше, чем первоначально ожидалось, или менее «дружественные» данные?
Для большинства вещей стоит поставить время вперед, чтобы создать достаточно эффективный и многообещающий алгоритм многократного использования, и просто не нужно беспокоиться, но иногда это может быть более сложным и подверженным ошибкам, а преимущества процессора или памяти просто не оправдывайте его. В конечном счете, это влияет на краткосрочные и долгосрочные последствия для вашего фактического проекта.
Довольно часто при создании алгоритмического кода существует мертвый, простой и понятный способ его решения, а также сложный, но эффективный способ его решения, и это хорошая идея быстро написать прежний код, чтобы вы могли использовать его для проверьте последний. Первое можно назвать реализацией «оракула», потому что ему доверяют знать правду: правильный ответ. Если это также происходит достаточно быстро, и у вас есть ограничения на n или сценарии данных, как обсуждалось, вам может не понадобиться переходить к сложной реализации.
Расширение на «мертвой, простой, очевидной способ его решения ». Возможно, вам придется выполнить одноразовую работу, которая заставит алгоритм n^2 на шесть часов решить после того, как вы написали несколько минут. Эффективный алгоритм может решить проблему через несколько минут, но вам понадобится час или два усилия по разработке. Вероятно, вам лучше работать с «неэффективным» алгоритмом, потому что вы можете запускать его в фоновом режиме во время работы над другими задачами. Я нахожусь в этом типе ситуации довольно регулярно и обнаружил, что «неэффективные» алгоритмы часто заканчивают тем, что экономят время. –
Есть 2^n опечатка для n^2? Я не думаю, что существуют разумные алгоритмы сортировки O (2^n). –
Я согласен, но довольно забавно, что я получил этот точный вопрос в экзаменационной статье, недавно используя 2^n – Dave
Это необычно. Тем не менее, возможно, O (n^2) может иметь смысл, если n элементов расположены в каком-то многомерном порядке со сложными требованиями или, возможно, вы можете считать что-то вроде упорядочивания набора чисел в решение для конкретной судоку «сортировки», их в распоряжение решения .... –