Вопросы о методах оценки увеличения времени выполнения алгоритма при увеличении размера ввода.
Существует множество вопросов о том, как анализировать время выполнения алгоритмов (см., Например, анализ времени выполнения и анализ алгоритма ). Многие из них похожи, например, те, которые запрашивают анализ затрат на вложенные циклы или алгоритмы «разделяй и властвуй», но большинство ответов,...
Часто говорят, что поиск в хеш-таблице работает в постоянное время: вы вычисляете значение хеш-функции, которое дает вам индекс для поиска в массиве. Все же это игнорирует столкновения; в худшем случае каждый предмет попадает в одно и то же ведро, и время поиска становится линейным (...
Поиск массив элементов с помощью бинарного поиска дублей, в худшем случае журнал 2 N итераций , потому что на каждом шаге мы подрезать половину нашего пространства поиска. Если бы вместо этого мы использовали «троичный поиск», мы бы вырезали две трети пространства поиска на каждой итерации, поэтому...
Сложность алгоритма разработана так, чтобы не зависеть от деталей более низкого уровня, но она основана на императивной модели, например, доступ к массиву и изменение узла в дереве занимают O (1) времени. Это не так в чисто функциональных языках. Список Haskell требует линейного времени для...
Я новичок в понимании алгоритмов информатики. Я понимаю процесс бинарного поиска, но у меня возникло небольшое недопонимание с его эффективностью. При размере элементов в среднем потребуется шагов, чтобы найти конкретный элемент. Взяв логарифм с обеих сторон 2, получим . Так не будет ли среднее...
Я даже не студент CS, так что это может быть глупым вопросом, но, пожалуйста, потерпите меня ... В до-компьютерную эпоху мы можем реализовать структуру данных массива только с чем-то вроде массива ящиков. Так как перед извлечением значения из него нужно найти ящик с соответствующим индексом,...
Википедия, а также другие источники, которые я обнаружил в списке voidтипа C как тип единицы, а не пустой тип. Мне кажется, что это сбивает с толку, так как мне кажется, что оно voidлучше подходит под определение пустого / нижнего типа voidНасколько я могу судить, ценности не обитают . Функция с...
В Википедии написано, что "... сортировка выбора почти всегда превосходит сортировку по пузырькам и сортировку по гномам". Кто-нибудь, пожалуйста, объясните мне, почему сортировка выбора считается быстрее, чем сортировка пузырьком, даже если они оба имеют: В худшем случае сложность времени : O (...
Прежде чем читать «Искусство компьютерного программирования» (TAOCP) , я не углублялся в эти вопросы. Я бы использовал псевдокод для описания алгоритмов, понимания их и оценки времени выполнения только по порядку роста. TAOCP тщательно меняет свое мнение. TAOCP использует английский, смешанный с...
Некоторые сложные алгоритмы ( объединение-поиск ) имеют почти постоянную обратную функцию Аккермана, которая появляется при асимптотической сложности времени, и являются оптимальными по времени в худшем случае, если почти постоянный обратный член Аккермана игнорируется. Существуют ли примеры...
Я заметил, что в нескольких исследовательских работах по CS, для сравнения эффективности двух алгоритмов, используется общее число ключевых сравнений в алгоритмах, а не реальное время вычислений. Почему мы не можем сравнить, какая из них лучше, запустив обе программы и посчитав общее время,...
У меня есть следующий код 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 )...
Рандомизированная быстрая сортировка - это расширение быстрой сортировки, в котором элемент поворота выбирается случайным образом. Что может быть наихудшим случаем временной сложности этого алгоритма. По моему мнению, это должно быть , так как наихудший случай случается, когда случайно выбранный...
Из ответов на (Когда) есть поиск в хэш-таблице O (1)? Я понимаю, что хеш-таблицы имеют O ( 1 )О(1)O(1) наихудшее поведение, по крайней мере амортизированное, когда данные удовлетворяют определенным статистическим условиям, и существуют методы, которые помогут сделать эти условия широкими. Однако, с...
В книге Марка де Берга и др. «Вычислительная геометрия: алгоритмы и приложения» описан очень простой алгоритм грубой силы для вычисления триангуляций Делоне. Алгоритм использует понятие недопустимых ребер - ребер, которые могут отсутствовать в допустимой триангуляции Делоне и должны быть заменены...
Алгоритм минимизации DFA Бжозовского создает минимальный DFA для DFA путем:граммGG обращая все ребра в , делая начальное состояние принимающим, а принимающее - начальным, чтобы получить NFA для обратного языка,N ′граммGGN'N′N' используя конструкцию powerset, чтобы получить для обратного...
Я читал эту книгу для своего класса рандомизированных алгоритмов. В этой конкретной книге есть целый раздел, посвященный поиску медианы массива с использованием случайного выбора, что приводит к более эффективному алгоритму. Теперь я хотел бы знать, есть ли какие-либо практические применения этого...
Я все еще немного путаюсь с терминами «длина ввода» и «размер ввода», когда они используются для анализа и описания бессимптомной верхней границы для алгоритма. Кажется, что длина входного сигнала для алгоритма зависит от типа данных и алгоритма, о котором вы говорите. Некоторые авторы ссылаются на...
На странице википедии об алгоритмах умножения упоминается интересная работа Дональда Кнута . По сути, это включает в себя объединение умножения с преобразованием Фурье с предварительно вычисленной таблицей умножений логарифмического размера. Это бежит в линейном времени. Статья действует так, будто...
У меня есть рекурсивный алгоритм с временной сложностью, эквивалентной выбору k элементов из n с повторением, и мне было интересно, смогу ли я получить более упрощенное выражение big-O. В моем случае может быть больше и они растут независимо.kkknnn В частности, я бы ожидал некоторого явного...