2
ответа
Оптимальный поиск k минимальные значения в неотсортированном списке целых чисел
У меня просто взяли интервью с вопросом, и мне любопытно, каков ответ должен быть. Проблема была по существу: Скажите, что у Вас есть неотсортированный список n целых чисел. Как Вы находите k минимальные значения в...
вопрос задан: 17 February 2009 21:25
1
ответ
Результат умножения обеих сторон отношения не-большой-O на одну и ту же функцию?
Следующее ли вообще верно? f∉O (g) ⇒ f * h∉O (g * h) где f, h, g - только положительные функции. Моя интуиция заключается в том, что это правда, но я не знаю, как это доказать. Вот почему я думаю, что это правда: ...
вопрос задан: 24 March 2019 02:42
1
ответ
Временная сложность рекурсивной функции с тремя рекурсивными вызовами
Какова будет временная сложность рекурсивной функции со следующим рекуррентным соотношением: T (n) = T (n-1) + T (n-2) + T (n-3), T (0) = T (1 ) = 1 и T (2) = 2 Я знаю, что функция с двумя ...
вопрос задан: 19 February 2019 05:14
1
ответ
Понимание того, когда использовать тета для временной сложности
Я (верю), я понимаю определения Big-O, Big-Ω и Big-Θ; в этом Big-O - асимптотическая верхняя граница, Big-Ω - асимптотическая нижняя граница, а Big-Θ - асимптотическая жесткая граница Однако я ...
вопрос задан: 15 January 2019 14:52
1
ответ
B-Tree VS Hash Thlat
В MySQL тип индекса - это B-дерево, и доступ к элементу в B-дереве находится в логарифмическом амортизированном времени O ( Журнал (n)). С другой стороны, доступ к элементу в хеш-таблице находится в O (1). Почему хеш ...
вопрос задан: 31 October 2017 18:18
1
ответ
Что такое O (журнал* N)?
Что такое O (журнал* N)? Я знаю большой о, журнал* неизвестен.
вопрос задан: 19 December 2015 18:23
1
ответ
Измерение сложности кода функционального языка и императивного языка
Каков наилучший способ сравнения сложности кода функционального языка и повелительный язык? В моем случае я должен сравнить сложность некоторых программ, написанных на F # и C ++.
На данный момент как ...
вопрос задан: 14 November 2013 21:29
1
ответ
Нахождение ближайших чисел Фибоначчи
Я пытаюсь решить более серьезную проблему и думаю, что важная часть программы тратится на неэффективные вычисления. Мне нужно вычислить для данного числа N интервал [P, Q], где P ...
вопрос задан: 20 October 2011 22:31
1
ответ
Асимптотическое время выполнения функции списка к дереву
У меня есть функция слияния, которая занимает время O (зарегистрируйте n) объединить два дерева в одно и функцию listToTree, которая преобразовывает первоначальный список элементов к одноэлементным деревьям и неоднократно обращается к слиянию...
вопрос задан: 18 April 2011 23:27
1
ответ
Сложная задача динамического программирования
Это смягченная версия задачи компьютерного зрения, которую мне нужно решить. Предположим, вам даны параметры n, q и вам нужно подсчитать количество способов присвоения целых чисел 0 .. (q-1) элементам n-by -...
вопрос задан: 13 November 2010 19:25
1
ответ
Почему перемещение от O (1) планировщик к CFS, который является O (регистрируют N)?
Я мог бы немного опоздать на этом, но я проходил, как различные производственные планировщики недавно работают, и я столкнулся с O (1) планировщик, который был заменен Абсолютно Справедливым Планировщиком, или...
вопрос задан: 15 August 2010 08:04
1
ответ
Использование повышения Bimap в C++
Повышение C++ имеет контейнер Bimap, который является двунаправленной картой: http://www.boost.org/doc/libs/1_43_0/libs/bimap/doc/html/index.html Делает любой знает выполнение Повышения:: bimap? Я имею в виду то, что является временем...
вопрос задан: 8 August 2010 22:34
1
ответ
Поиск по словарю (O (1)) по сравнению с Linq, где
Что быстрее, и я должен пожертвовать стандартом Linq для достижения скорости (предполагающий, что Поиск по словарю действительно быстрее)? Таким образом позвольте мне уточнить: у Меня есть следующее: Список <продукт> продукты =...
вопрос задан: 16 March 2010 16:31
1
ответ
Методы для сокращения сложности в игровом [закрытом] программировании
В мое свободное время я программирую игры как хобби, различные виды вещей и в настоящее время ничего очень сложного. Вещам нравятся 2-е стрелки, Основанные на мозаике игры, Головоломки, и т.д... Однако как разработка...
вопрос задан: 27 January 2010 07:41
1
ответ
Есть ли какие-либо алгоритмы онлайн для тестирования планарности?
Я знаю, что тестирование планарности может быть сделано в O (v) (эквивалентно O (e), так как плоские графики имеют O (v) края), время. Интересно, может ли это быть сделано онлайн в O (1) амортизируемое время, поскольку каждый край добавляется (все еще...
вопрос задан: 21 October 2009 17:19
1
ответ
Понимание алгоритма Ukkonen для суффиксных деревьев [дубликат]
Я делаю некоторую работу с алгоритмом Ukkonen для создания суффиксных деревьев, но я не понимаю некоторые части объяснения автора, поскольку это - линейно-разовая сложность. Я изучил алгоритм...
вопрос задан: 20 August 2009 07:11
1
ответ
Алгоритм банкира вычислил временную сложность
Алгоритм банкира используется, чтобы определить, могут ли все запросы на ресурсы быть удовлетворены, не ведя к мертвой блокировке. m является общим количеством n типов ресурсов, общее количество процессов...
вопрос задан: 19 August 2009 11:13
1
ответ
Действительно ли минимизация булевых выражений полна NP?
Я знаю, что булева выполнимость Полна NP, но является минимизацией/упрощением булева выражения, которым я означаю брать данное выражение в символьной форме и производить...
вопрос задан: 1 March 2009 16:42
0
ответов
Какой большой О у функции (log n) ^ k
Какова сложность большого О функции (log n) k для любого k?
вопрос задан: 16 October 2019 05:37
0
ответов
Эффективные алгоритмы для вычисления матрицы, умноженной на ее транспонирование [закрыто]
Для класса вопрос, который был задан моим учителем, заключался в алгоритмической стоимости умножения матрицы на ее транспонировать. При стандартном алгоритме умножения матриц с тремя циклами эффективность составляет O (...
вопрос задан: 31 July 2019 06:49
0
ответов
Интуитивное объяснение того, почему QuickSort является n log n?
Кто-нибудь может дать интуитивно понятное, но формальное объяснение того, что делает QuickSort n log n? Насколько я понимаю, он должен пройти через n элементов, и он делает это n раз......
вопрос задан: 26 June 2019 08:10
0
ответов
Пример O (n!)?
Какой пример (в коде) функции O (n!)? Для выполнения по отношению к n должно потребоваться соответствующее количество операций; то есть я спрашиваю о временной сложности.
вопрос задан: 4 June 2019 08:20
0
ответов
Создать заданную строку из словарных статей
Во время недавнего собеседования меня попросили дать решение следующей проблемы: учитывая строку s (без пробелов) и словарь, вернуть слова в словаре, составляющие строку.
...
вопрос задан: 16 March 2019 12:44
0
ответов
Как улучшить цикломатическую сложность?
Цикломатическая сложность будет высокой для методов с большим количеством операторов принятия решений, включая операторы if / while / for. Итак, как нам это улучшить? Я занимаюсь большим проектом, в котором я нахожусь ...
вопрос задан: 5 January 2019 11:29
0
ответов
Сглаживание вложенных циклов / уменьшение сложности - алгоритм подсчета дополнительных пар
Недавно я пытался решить некоторую задачу на Python и нашел решение, которое, кажется, имеет сложность O (n log n), но я считаю, что это очень неэффективно для некоторых входных данных (например, first ...
вопрос задан: 16 October 2018 13:23
0
ответов
Временная сложность создания Суффиксного дерева
Для создания суффиксного дерева, в худшем корпусе, если бы вся буква последовательности отличается сложность, была бы чем-то как n + (n-1) + (n-2)... 1 = n* (n+1)/2, который является O (n^2). Однако...
вопрос задан: 5 October 2018 19:00
0
ответов
Имеют ли итерационные и рекурсивные версии алгоритма одинаковую временную сложность?
Скажем, например, итеративная и рекурсивные версии ряда Фибоначчи. У них одинаковая временная сложность?
вопрос задан: 30 September 2018 08:02
0
ответов
В поисках Большой О Гармонической Серии
Докажите, что 1 + 1/2 + 1/3 + ... + 1 / n есть O (log n). Предположим, что n = 2 ^ k, я положил ряд в сумму, но я понятия не имею, как решить эту проблему. Любая помощь приветствуется
вопрос задан: 20 April 2018 08:35
0
ответов
Какова сложность алгоритма деления пополам?
Я написал код, чтобы понять, какой из них быстрее, когда дело доходит до поиска элемента в списке. Получается биссектриса. Чего я не понимаю, так это того, какова сложность алгоритма деления пополам и что делает...
вопрос задан: 8 March 2018 15:58
0
ответов
Как найти временную сложность алгоритма
Вопрос Как найти временную сложность алгоритма? Что я сделал, прежде чем опубликовать вопрос о SO? Я прошел через это, это и многие другие ссылки, но не там, где я смог найти ...
вопрос задан: 27 October 2017 07:38