Использование как можно меньшего количества ресурсов (например, времени, пространства) при решении проблемы. Используйте этот тег, если ваш вопрос касается именно использования ресурсов, а не вопросов общего алгоритма, в которых упоминается время выполнения.
Взглянув на веб-страницу Джулии , вы можете увидеть некоторые тесты нескольких языков по нескольким алгоритмам (время показано ниже). Как может язык с компилятором, изначально написанным на C, превзойти C-код? Рисунок: время тестов относительно C (чем меньше, тем лучше, производительность C =...
Почему в информатике любая сложность, которая в большинстве случаев является полиномиальной, считается эффективной? Для любого практического применения (a) алгоритмы со сложностью работают намного быстрее, чем алгоритмы, выполняющиеся во времени, скажем, , но первый считается неэффективным, а...
Предположим, что я программист, и у меня есть NP-полная проблема, которую мне нужно решить. Какие методы доступны для решения проблем с NPC? Есть опрос или что-то похожее на эту...
Я знаю, как кодировать для факториалов, используя итеративные и рекурсивные (например, n * factorial(n-1)например). Я прочитал в учебнике (без каких-либо дальнейших объяснений), что существует еще более эффективный способ кодирования для факториалов, разделив их пополам рекурсивно. Я понимаю,...
Каков был бы самый быстрый способ сделать это (с алгоритмической точки зрения, а также с практической точки зрения)? Я думал что-то вроде следующего. Я мог бы добавить в конец массива и затем использовать пузырьковую сортировку, так как она имеет наилучший случай (полностью отсортированный массив в...
Поскольку покупка вычислительных мощностей гораздо более доступна, чем в прошлом, становятся ли менее важными знания алгоритмов и эффективность? Понятно, что вы хотели бы избежать бесконечного цикла, поэтому не все идет. Но если бы у вас было лучшее аппаратное обеспечение, вы могли бы иметь...
В Википедии написано, что "... сортировка выбора почти всегда превосходит сортировку по пузырькам и сортировку по гномам". Кто-нибудь, пожалуйста, объясните мне, почему сортировка выбора считается быстрее, чем сортировка пузырьком, даже если они оба имеют: В худшем случае сложность времени : O (...
Я ищу структуру данных, которая поддерживает эффективный приблизительный поиск ключей (например, расстояние Левенштейна для строк), возвращая максимально возможное совпадение для клавиши ввода. Наилучшей структурой данных, которую я нашел до сих пор, являются деревья Буркхарда-Келлера , но мне было...
Я изучаю кратчайшие пути в ориентированных графах в настоящее время. Существует много эффективных алгоритмов для поиска кратчайшего пути в сети, например, dijkstra или bellman-ford. Но что, если график является динамическим? Говоря динамически, я имею в виду, что мы можем вставлять или удалять...
Я пытаюсь получить представление о том, как следует интерпретировать тест простоты AKS, когда узнаю о нем, например, следствие для доказательства того, что PRIMES ⊆ P, или действительно практичный алгоритм тестирования простоты на компьютерах. Тест имеет полиномиальное время выполнения, но с...
Я готовлюсь к собеседованию по кодированию и не могу найти самый эффективный способ решения этой проблемы. Допустим, у нас есть два массива, состоящих из несортированных чисел. Массив 2 содержит число, которого нет в массиве 1. Оба массива имеют случайно расположенные числа, не обязательно в одном...
Знаете ли вы какой-либо алгоритм, который эффективно рассчитывает факториал после модуля? Например, я хочу запрограммировать: for(i=0; i<5; i++) sum += factorial(p-i) % p; Но pэто большое число (простое число) для непосредственного применения факториала .( р ≤ 108)(п≤108)(p \leq 10^ 8) В Python...
Предположим, нам даны два числа и и мы хотим найти для .lllrrrmax(i⊕j)max(i⊕j)\max{(i\oplus j)}l≤i,j≤rl≤i,j≤rl\le i,\,j\le r Наивный алгоритм просто проверяет все возможные пары; например, в ruby у нас будет: def max_xor(l, r) max = 0 (l..r).each do |i| (i..r).each do |j| if (i ^ j > max) max...
Я только начал читать о теории вычислений. Если мы сравним, что является более мощным (в принятии строк), оба одинаковы. Но как насчет эффективности? DFA будет быстрым по сравнению с NFA, поскольку у него есть только один исходящий фронт, и не будет никакой двусмысленности. Но в случае NFA мы...
Динамическое программирование может сократить время, необходимое для выполнения рекурсивного алгоритма. Я знаю, что динамическое программирование может помочь уменьшить временную сложность алгоритмов. Являются ли общие условия такими, чтобы при выполнении рекурсивного алгоритма подразумевалось, что...
Таким образом, сортировка слиянием - это алгоритм «разделяй и властвуй». Пока я смотрел на приведенную выше диаграмму, я думал, можно ли вообще обойти все этапы разделения. Если вы перебираете исходный массив при переходе на два, вы можете получить элементы по индексам i и i + 1 и поместить их в...
Я пытаюсь составить список алгоритмов / задач, которые являются «исключительно полезными», например, при решении задач, которые «кажутся» очень экспоненциальными по своей природе, но имеют какой-то особенно умный алгоритм, который в конечном итоге решает их. Примеры того, что я имею в виду:...
Я наткнулся на этот рисунок, который показывает, что контекстно-свободные и регулярные языки являются (правильными) подмножествами эффективных задач (предположительно ). Я прекрасно понимаю, что эффективные проблемы являются подмножеством всех разрешимых проблем, потому что мы можем их решить, но...
Динамическое программирование с большим количеством подзадач. Поэтому я пытаюсь решить эту проблему с улицы Интервью: Ходьба по сетке (оценка 50 баллов) Вы находитесь в мерной сетке в позиции . Размеры сетки: ). За один шаг вы можете идти на один шаг вперед или назад в любом из измерений. (Так что...
Алгоритм машины Тьюринга за полиномиальное время считается эффективным, если его время выполнения, в худшем случае, ограничено полиномиальной функцией входного размера. Мне известен сильный тезис Черча-Тьюринга: Любая разумная модель вычислений может быть эффективно смоделирована на машинах...