Вопросы о науке и искусстве определения свойств алгоритмов, часто включая правильность, время выполнения и использование пространства. Используйте тег [runtime-analysis] для вопросов о времени выполнения алгоритмов.
Существует множество вопросов о том, как анализировать время выполнения алгоритмов (см., Например, анализ времени выполнения и анализ алгоритма ). Многие из них похожи, например, те, которые запрашивают анализ затрат на вложенные циклы или алгоритмы «разделяй и властвуй», но большинство ответов,...
Чтобы попытаться проверить, является ли алгоритм для какой-либо проблемы правильным, обычная отправная точка состоит в том, чтобы попытаться запустить алгоритм вручную на нескольких простых тестовых примерах - попробуйте на нескольких примерах проблемных примеров, включая несколько простых «угловых...
Обычно в алгоритмах мы не заботимся о сравнении, сложении или вычитании чисел - мы предполагаем, что они выполняются за время . Например, мы предполагаем это, когда говорим, что сортировка на основе сравнения - это O ( n log n ) , но когда числа слишком велики, чтобы поместиться в регистры, мы...
Часто говорят, что поиск в хеш-таблице работает в постоянное время: вы вычисляете значение хеш-функции, которое дает вам индекс для поиска в массиве. Все же это игнорирует столкновения; в худшем случае каждый предмет попадает в одно и то же ведро, и время поиска становится линейным (...
Поиск массив элементов с помощью бинарного поиска дублей, в худшем случае журнал 2 N итераций , потому что на каждом шаге мы подрезать половину нашего пространства поиска. Если бы вместо этого мы использовали «троичный поиск», мы бы вырезали две трети пространства поиска на каждой итерации, поэтому...
Я читаю книгу под названием « Принципы информатики» (2008) Карла Рейнольдса и Пола Тиманна (опубликована в «Схемах Шаума»). Во второй главе представлены алгоритмы с примером последовательного поиска, который просто перебирает список имен и возвращает TRUE, если в списке найдено данное имя. Автор...
Сложность алгоритма разработана так, чтобы не зависеть от деталей более низкого уровня, но она основана на императивной модели, например, доступ к массиву и изменение узла в дереве занимают O (1) времени. Это не так в чисто функциональных языках. Список Haskell требует линейного времени для...
Мне интересно, есть ли стандартный способ измерения "сортировки" массива? Будет ли массив с медианным числом возможных инверсий считаться максимально несортированным? Под этим я подразумеваю, что это в основном как можно дальше от сортировки или обратной...
Хорошо известно, что этот «наивный» алгоритм перестановки массива путем замены каждого элемента на другой, случайно выбранный, не работает правильно: for (i=0..n-1) swap(A[i], A[random(n)]); В частности, поскольку на каждой из итераций делается один из вариантов (с одинаковой вероятностью),...
Я даже не студент CS, так что это может быть глупым вопросом, но, пожалуйста, потерпите меня ... В до-компьютерную эпоху мы можем реализовать структуру данных массива только с чем-то вроде массива ящиков. Так как перед извлечением значения из него нужно найти ящик с соответствующим индексом,...
Я получил задание в моем университете. Я взял его домой и попытался запрограммировать алгоритм для его решения, это было что-то, связанное с графиками, поиск связанных компонентов, я думаю. Затем я сделал самую тривиальную вещь, которая пришла мне в голову, а затем показала моему лектору. После...
У меня есть жадный алгоритм, который, я подозреваю, может быть правильным, но я не уверен. Как мне проверить, правильно ли это? Какие методы использовать для доказательства правильности жадного алгоритма? Существуют ли общие модели или методы? Я надеюсь, что это станет справочным вопросом, на...
Википедия, а также другие источники, которые я обнаружил в списке voidтипа C как тип единицы, а не пустой тип. Мне кажется, что это сбивает с толку, так как мне кажется, что оно voidлучше подходит под определение пустого / нижнего типа voidНасколько я могу судить, ценности не обитают . Функция с...
Ли сглаженный анализ найти свой путь в основной анализ потока алгоритмов? Обычно разработчики алгоритмов применяют сглаженный анализ к своим
Чтобы сформулировать вопрос, в информатике часто мы хотим вычислить произведение нескольких вероятностей: P(A,B,C) = P(A) * P(B) * P(C) Самый простой подход - просто умножить эти числа, и это то, что я собирался сделать. Однако мой начальник сказал, что лучше добавить журнал вероятностей:...
Некоторые сложные алгоритмы ( объединение-поиск ) имеют почти постоянную обратную функцию Аккермана, которая появляется при асимптотической сложности времени, и являются оптимальными по времени в худшем случае, если почти постоянный обратный член Аккермана игнорируется. Существуют ли примеры...
Иногда легко определить временную сложность алгоритма, если внимательно его изучить. Алгоритмы с двумя вложенными циклами , очевидно, N 2 . Алгоритмы , которые исследуют все возможные комбинации N групп из двух значений, очевидно , 2 N .NNNN2N2N^2NNN2N2N2^N Однако я не знаю, как «определить»...
Я заметил, что в нескольких исследовательских работах по CS, для сравнения эффективности двух алгоритмов, используется общее число ключевых сравнений в алгоритмах, а не реальное время вычислений. Почему мы не можем сравнить, какая из них лучше, запустив обе программы и посчитав общее время,...
Меня интересует вопрос об асимптотическом времени выполнения алгоритма Укконена , возможно, самого популярного алгоритма построения суффиксных деревьев за линейное (?) Время. Вот цитата из книги «Алгоритмы на строках, деревьях и последовательностях» Дэна Гасфилда (раздел 6.5.1): »... в...
У меня есть следующий код Python. def collatz(n): if n <= 1: return True elif (n%2==0): return collatz(n/2) else: return collatz(3*n+1) Каково время работы этого алгоритма? Пытаться: Если обозначает время работы функции . Тогда я думаю, что у меня { T ( n ) = 1 для n ≤ 1 T ( n ) = T ( n / 2 )...