сложность алгоритма [закрывается]
Вы можете сделать просто:
k <- list('test', 'one')
k[which.max(lapply(k, nchar))]
[[1]]
[1] "test"
8 ответов
Если Вы пишете часть программного обеспечения, и можно думать о нескольких способах реализовать его, часто один из решающих факторов (в дополнение к концептуальной сложности и время для реализации) будет алгоритмической сложностью. Таким образом, когда Ваш босс хочет выравнивание для Вашего решения, выясняя, что сложность каждого необходима. В то время как некоторые могут считать это формой преждевременной оптимизации, я думаю, что согласие состоит в том, что выбор дизайна, подходящего для Вашей проблемы, является просто хорошей разработкой программного обеспечения.
Конечно! В любое время Вы делаете что-то по миллион раз, Вы могли бы хотеть проверить свой алгоритм.
Один экземпляр, который я сделал, был, когда я генерировал миллионы изображений, которые должны были поместиться в шаблон сетки. Извините - не может стать намного более специфичным для того.
Я не знаю, рассматриваете ли Вы конкурсы программирования как школу или нет, но видеть, можно ли решить проблему конкурса (с указанными ограничениями размера задач) в ограничении по времени, необходимо примерно оценить количество операций путем считания сложности алгоритма используемой.
На работе мы небрежно обсуждаем переменные алгоритмы для решения проблемы, и сложность играет свою роль. Это никогда не что-то, где мы должны сделать строгие доказательства сложности, но просто генерала, "мы могли сделать X, но это будет O (N^2), который является слишком много, потому что мы могли выполнять итерации более чем миллионов строк".
Сверхоптимизация может привести к плохому коду, но знание сложности Вашего основного алгоритма имеет большое значение в определении лучшего способа решить проблему программирования.
Да и нет.
Я писал инструмент для выравнивания зависимостей от об/мин ряда пакетов в единственную цепочку. Очевидное решение работало слишком медленно, таким образом, я вырыл через свою память немного для запоминания a O(n+m) алгоритм от класса теории графов. Я сделал немного быстро и легко определяемого вычисления, чтобы удостовериться, что это действительно было O(n+m), затем записал это и ввел его в эксплуатацию :)
Я не знаю, что на самом деле записываю вещи, но все время я оцениваю, как я создаю свои алгоритмы, чтобы видеть, могу ли я повысить эффективность его. Для кода я спрашиваю меня, если существует способ превратить вложенные циклы в единственный цикл или от цикла до использования деления и завоевать подход. Это было бы эквивалентно движению от O (N2) к O (N) и O (N) к O (log2N). То же верно для SQL - может я удалять соединение и делают подзапрос вместо этого с помощью индекса - возможно, идущий от O (N2) к O (N) (или даже O (1), если это включает мне к индексируемым запросам на обеих таблицах).
Да.
Обычно сложность достаточно очевидна для предположений салфетки, и это хорошо для разработки, пока я не перехожу к сути дела, где я должен измерить уровень. Во многих случаях раздел, по поводу которого я волновался, прекрасен (т.е., предположение салфетки было достаточно хорошо), и что-то еще замедляет программное обеспечение. Почти во всех случаях это платит, чтобы пойти с моими основными предположениями и измерить уровень позже.
Однако, когда я делаю очень строго ограниченный во времени код, особенно в графическом рендеринге, я действительно сажусь и определяю сложность алгоритма и компромиссы, связанные с выполнением его альтернативным способом.
Сегодня я работаю с кем-то еще код, и это страшно медленно. Я действительно не забочусь - может потребоваться 10 минут для всего, что это имеет значение для полного процесса, который это улучшает. Но я должен был посмотреть на код для исправления ошибки, и у этого человека есть циклы в циклах в циклах, большинство из них ищет тот же список тот же путь к другому элементу каждый раз. В сущности он изменил хороший arrayfunction, скажите func (i) {записи возврата [я];} в ужасную поисковую стандартную программу:
func(i)
{
for each index in records
if i==index return records[index]
next
}
Действительность намного хуже, но Вы получаете идею.
Причина Вы изучаете это в школе теперь, так, Вы видите эти структуры и автоматически категоризируете их. Вы, вероятно, не будете нуждаться к на самом деле компьютеру или уменьшать его до хорошего аккуратного числа сложности, но если Вы не будете делать этого теперь вручную и видеть многое из него, то Вы также будете производить код как этот, и у Вас просто не будет подсказки.
- Adam
Абсолютно - у нас просто недавно была проблема с нашим приложением где все это внезапного запущенного удара некоторого основного замедления. Оказалось, что у нас было кубическое (O (n^3)) алгоритм прямо в середине очень главной функции. Это было скрыто под слоями абстракции. Выяснение, что произошло требуемое планирование графика вызова функции и рассмотрение деталей.
По общему признанию, после того как мы сделали это, это не похоже, я должен был применить любую математику для замечания O (n^3) алгоритм, но это главным образом, потому что 3 года Анализа Алгоритмов в университете дали мне общее чувство для того, на что похож кубический алгоритм.
Так или иначе оказывается, что N увеличился просто немного, но это прямо в остром выступе движения от взятия нескольких сотен миллисекунд к взятию пары секунд и затем в минуты - так проблема не показало вплоть до просто недавно.
По большей части Вы собираетесь быть предварительно упакованными алгоритмами использования, которые определили сложности. Quicksort является O (n^2) худший случай и O (n*log (n)) средний случай, двоичный поиск является O (журнал (n)) и т.д. библиотеки будут обычно указывать то, что их рабочие характеристики, и только необходимо волноваться о том, как они сочиняют.