1
ответ
Результат умножения обеих сторон отношения не-большой-O на одну и ту же функцию?
Следующее ли вообще верно? f∉O (g) ⇒ f * h∉O (g * h) где f, h, g - только положительные функции. Моя интуиция заключается в том, что это правда, но я не знаю, как это доказать. Вот почему я думаю, что это правда: ...
вопрос задан: 24 March 2019 02:42
1
ответ
В git, с какой скоростью увеличивается размер, если каждое изменение символа является коммитом?
Я пытаюсь понять, как работает Git. Если бы мне пришлось изменить (добавить или удалить) символ, сохраните и зафиксируйте это изменение до тех пор, пока не будет написан мой код. Как будет увеличиваться размер по мере увеличения размера файла? За ...
вопрос задан: 20 March 2019 14:59
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
ответ
Каковы гарантии сложности стандартных контейнеров?
Очевидно ;-) стандартные контейнеры предоставляют некоторую форму гарантий. Какого рода гарантии и каковы различия между различными типами контейнеров? Работаю из SGI ...
вопрос задан: 21 March 2018 04:35
1
ответ
Быстрая сортировка Худший случай
Я работаю над программой, которая необходима для того, чтобы понять ее лучше. Какое наихудшее время выполнения для быстрой сортировки и что может привести к ухудшению производительности? Как мы можем изменить ...
вопрос задан: 27 February 2018 00:14
1
ответ
Сложность реверсирования строки [дубликат]
Если бы я должен был изменить строку, используя: «hello there!» [:: - 1] Будет ли это O (n), потому что алгоритм должен отменить больше символов, если входная строка больше?
вопрос задан: 3 June 2016 05:06
1
ответ
Какая большая O-нотация методов Map.prototype.has и Set.prototype.has в Javascript? [Дубликат]
Каковы большие O-обозначения методов Javascript Map.prototype.has и Set.prototype.has? Согласно документации для Set: Выполняются следующие шаги: Пусть S - это значение ....
вопрос задан: 27 June 2015 17:59
1
ответ
Есть ли тип данных списка Hashable? [Дубликат]
Возможно, это очень пустой вопрос. Сложность поиска элемента из списка - O (n) (если список отсортирован, он может быть выполнен в O (log n), который лучше). Однако сложность ...
вопрос задан: 3 November 2014 22:58
1
ответ
Временная сложность алгоритма Евклида
Мне трудно решить, какова временная сложность алгоритма наибольшего общего знаменателя Евклида. Этот алгоритм в псевдокоде: function gcd (a, b) while b ≠ 0 t: = b ...
вопрос задан: 11 March 2014 01:57
1
ответ
Инструмент Algorithm Analysis для [закрытого] Java
Я ищу аналитический инструмент алгоритма для Java, который может вычислить Большую 0 из функции. Идеал я хотел бы сделать это частью моего процесса сборки вдоль стороны моего другого метрического инструмента кода. Даже...
вопрос задан: 14 November 2013 21:29
1
ответ
Какова сложность сортировки ведер O(n+k), если мы реализуем сортировку ведер с использованием связанных списков?
Мне любопытно, почему сортировка ведер имеет время исполнения O(n+k), если мы используем ведра, реализованные с использованием связанных списков. Например, предположим, что у нас есть этот вход: n = no of element= 8
k = диапазон = 3 массива =...
вопрос задан: 9 May 2013 15:55
1
ответ
Доказательство и опровержение BigO
В доказательстве и опровержении Больших вопросов O, который, поскольку, которые явно говорят, используют определение, чтобы доказать и опровергнуть, мой вопрос, является тем, что я делаю корректный? Например, у Вас есть вопрос, который является g (n) = O
вопрос задан: 19 September 2012 16:25
1
ответ
Асимптотическое время выполнения функции списка к дереву
У меня есть функция слияния, которая занимает время O (зарегистрируйте n) объединить два дерева в одно и функцию listToTree, которая преобразовывает первоначальный список элементов к одноэлементным деревьям и неоднократно обращается к слиянию...
вопрос задан: 18 April 2011 23:27
1
ответ
Какова вычислительная сложность MapReduce наверху
Учитывая, что сложность карты и уменьшает задачи, O (карта) =f (n), и O (уменьшают) =g (n), имеет кого-либо занявшего время, чтобы записать как Отображение/Уменьшение внутренних операций (сортировка, перестановка, отправка...
вопрос задан: 26 September 2010 23:14
1
ответ
Каков BigO линейной регрессии?
Насколько большой система - это разумный, чтобы попытаться сделать линейную регрессию на? Конкретно: у Меня есть система с ~300K точками выборки и ~1200 линейными членами. Это в вычислительном отношении выполнимо?
вопрос задан: 23 December 2009 20:22
1
ответ
Найдите два числа в дереве двоичного поиска, которые составляют в целом третье число
Вам дают BST чисел. Необходимо найти два числа (a, b) в нем таким образом что + b = S, в O (n) время и O (1) пространство. Каков мог быть алгоритм? Один возможный путь мог быть два, преобразовывают BST...
вопрос задан: 18 November 2009 08:02
0
ответов
Какой большой О у функции (log n) ^ k
Какова сложность большого О функции (log n) k для любого k?
вопрос задан: 16 October 2019 05:37
0
ответов
Пример O (n!)?
Какой пример (в коде) функции O (n!)? Для выполнения по отношению к n должно потребоваться соответствующее количество операций; то есть я спрашиваю о временной сложности.
вопрос задан: 4 June 2019 08:20
0
ответов
Как определить пространственно-временную сложность этой функции
Я пытаюсь определить пространственно-временную сложность функции, которую я написал, чтобы я мог обсудить эту функцию в терминах асимптотических границ в своем отчете. Дан список списков, где каждый ...
вопрос задан: 30 March 2019 23:58
0
ответов
Сравнение сортировки и обмен Shell
У меня возникают трудности с пониманием того, производит ли мой код правильное количество обменов (свопов) и сравнений. Я получаю один и тот же номер для всех трех случаев, который не похож на вставку ...
вопрос задан: 27 March 2019 00:05
0
ответов
Пространственно-временная сложность поиска в массиве элементов, упорядоченных по убыванию
В главе 11 «Элементы программирования интервью в Python (EPI)», которая фокусируется на бинарном поиске, приведен следующий фрагмент кода: из коллекций импортируется namedtuple из набора текста ...
вопрос задан: 5 March 2019 01:06
0
ответов
Время выполнения цикла for с доступом к массиву
Если у меня есть цикл for, где для каждого индекса я обращаюсь к массиву [i], массиву [i-1], массиву [i + 1], он все еще будет работать в O (n), предполагая, что весь доступ постоянен? Пример: for (int i = 1; i < array.length-1; i ++ ...
вопрос задан: 2 March 2019 15:53
0
ответов
Лучший способ получить пересечение ключей двух объектов?
У меня есть два литерала объекта, например, так: var firstObject = {x: 0, y: 1, z: 2, a: 10, b: 20, e: 30} var secondObject = {x: 0, y: 1, z: 2, а: 10, с: 20, ...
вопрос задан: 29 January 2019 21:41
0
ответов
Проблема смены монет: разница между этими двумя методами
Я реализую проблему изменения монеты в Python в CS50 в pset6. Когда я впервые решил эту проблему, я использовал алгоритм: время импорта, в то время как True: try: totalChange = input ('...
вопрос задан: 31 December 2018 12:49
0
ответов
Временная сложность создания Суффиксного дерева
Для создания суффиксного дерева, в худшем корпусе, если бы вся буква последовательности отличается сложность, была бы чем-то как n + (n-1) + (n-2)... 1 = n* (n+1)/2, который является O (n^2). Однако...
вопрос задан: 5 October 2018 19:00
0
ответов
Какова временная сложность перебора карты std ::set/std ::?
Какова временная сложность итерации по стандартному ::набору/стандартному ::мультинабору/стандартному ::карте/стандартному ::мультикарте? Я считаю, что это линейно по размеру набора/карты, но не уверен. Указано ли в...
вопрос задан: 24 August 2018 00:06
0
ответов
В поисках Большой О Гармонической Серии
Докажите, что 1 + 1/2 + 1/3 + ... + 1 / n есть O (log n). Предположим, что n = 2 ^ k, я положил ряд в сумму, но я понятия не имею, как решить эту проблему. Любая помощь приветствуется
вопрос задан: 20 April 2018 08:35
0
ответов
Является ли 2 ^ (2n) = O (2 ^ n)
Является ли 2 (n + 1) = O (2n)? Я считаю, что это правильно, потому что n + 1 ~ = n. 2 (2n) = O (2n)? Кажется, что в этом будет та же логика, но я не уверен.
вопрос задан: 31 March 2018 10:08
0
ответов
Определите, появляется ли число только один раз в массиве
Это своего рода домашнее задание, я долго об этом думал и придумал пару решений, но я думаю, что есть лучшее решение. Какой самый быстрый способ определить, если ...
вопрос задан: 10 December 2017 06:55