0
ответов
Обязательна ли быстрая сортировка на месте (на месте) или нет?
Быстрая сортировка часто описывается как алгоритм на месте (на месте), несмотря на то, что он требует места в стеке O (log n). То есть in situ означает «требуется меньше O (n) дополнительного пространства» или складывается ...
вопрос задан: 11 August 2014 13:19
0
ответов
Ищу специальную структуру данных C ++
Я ищу реализацию C ++ структуры данных (или комбинации структур данных), которая удовлетворяет следующим критериям: доступ к элементам осуществляется так же, как в std :: вектор
предоставляет случайные ...
вопрос задан: 24 June 2014 14:32
0
ответов
Уменьшение сложности полиномиального умножения
I пытались вычислить это в течение 3 дней и ничего не добились. Мне нужно реализовать полиномиальное умножение (умножить 2 квадратных уравнения). Они выглядят так: (a1 x ^ 2 + b1 x + c1) * (...
вопрос задан: 7 June 2014 20:48
0
ответов
алгоритм для поиска самых длинных неперекрывающихся последовательностей
Я пытаюсь найти лучший способ решить следующую проблему. Под лучшим способом я подразумеваю менее сложный. На входе список кортежей (начало, длина), например: [(0,5), (0,1), (1,9), (5,5), (5,7), (10,1) ] Каждый ...
вопрос задан: 3 June 2014 21:52
0
ответов
Наблюдение за квадратичным поведением с помощью быстрой сортировки - O (n ^ 2)
Алгоритм быстрой сортировки имеет среднюю временную сложность O (n * log (n)) и худший случай сложность O (n ^ 2). Предполагая некоторый вариант алгоритма быстрой сортировки Хоара, какие входные данные будут вызывать ...
вопрос задан: 29 May 2014 13:02
0
ответов
как определить, является ли k-й самый большой элемент кучи больше x
Рассмотрим двоичную кучу, содержащую n
числа (в корне хранится наибольшее число). Вам дается
положительное целое число k
вопрос задан: 24 April 2014 04:56
0
ответов
Отслеживание медианы расширяющегося массива
Вопрос на интервью: Отредактировано ниже
Вам дан массив. Вы делаете из него 2 кучи: одну минимальную, а другую - максимальную. Теперь найдите медианное значение массива, используя эти 2 предоставленные кучи в O (nlog n) ...
вопрос задан: 1 April 2014 13:48
0
ответов
Почему Java не включает временную/пространственную сложность каждой функции в javadoc?
Здравствуйте, я хочу знать, какова временная сложность функции replaceAll класса String, но я не могу найти об этом никакой информации (http://docs.oracle.com/javase/6/docs). /api/java/lang/String.html) ...
вопрос задан: 22 November 2013 21:53
0
ответов
Временная сложность A*
Википедия говорит о сложности A* следующее: Временная сложность A* зависит от эвристики. В худшем случае количество расширяемых узлов экспоненциально зависит от длины решения...
вопрос задан: 24 October 2013 19:00
0
ответов
Решение рецидивов T (N) = √n T (√n) + N [Закрыто]
Возможно ли решить отношение рецидивов T (n) = √n t (√n) + n Мастер Теорема? Это не форма t (n) = a ⋅ t (n / b) + f (n), но эта проблема приводится в упражнениях ...
вопрос задан: 27 September 2013 17:05
0
ответов
Обнаружение повторяющегося элемента в массиве
Существует массив размера n, и элементы, содержащиеся в массиве, находятся в диапазоне от 1 до n-1, так что каждый элемент встречается один раз, а только один элемент встречается более одного раза. Нам нужно найти этот элемент. ...
вопрос задан: 25 September 2013 23:30
0
ответов
Распределение людей по зданиям с соблюдением предпочтений?
Сегодня друг задал мне вопрос о задаче о присваивании. Я нашел довольно простое решение, но я чувствую, что его можно сделать проще и быстрее.
Ваша помощь будет оценена по достоинству. ...
вопрос задан: 14 June 2013 17:57
0
ответов
Каков худший случай для алгоритма поиска строки KMP? [закрыто]
Может ли кто-нибудь предложить мне наихудший вариант «пара текстовая строка - шаблон» для тестирования реализации алгоритма KMP?
вопрос задан: 29 May 2013 21:50
0
ответов
Временная сложность кортежа в Python
Аналогичный вопрос по хешу (словари) и списки, здесь также есть полезная информация: http://wiki.python.org/moin/TimeComplexity Но я ничего не нашел о кортежах. Доступ ...
вопрос задан: 9 May 2013 10:46
0
ответов
Временная сложность find()в std::map?
Насколько эффективна функция find()в классе std::map? Перебирает ли он все элементы в поисках ключа так, чтобы он был O(n), или он находится в сбалансированном дереве, или использует хеш...
вопрос задан: 30 January 2013 20:04
0
ответов
Разница между O (n )и O (log (n))-что лучше и что такое O (log (n ))?
Это мой первый курс по структурам данных и на каждой лекции/лекции ТА мы говорим об O(log(n)). Вероятно, это глупый вопрос, но я был бы признателен, если бы кто-нибудь объяснил мне, что именно делает...
вопрос задан: 17 January 2013 09:16
0
ответов
В чем сложность этого простого фрагмента кода?
Я вставляю этот текст из имеющейся у меня электронной книги. Он говорит о сложности, если O (n2), а также дает объяснение, но я не вижу, как это сделать. Вопрос: Каково время работы этого кода? public ...
вопрос задан: 5 January 2013 06:44
0
ответов
Асимптотический анализ трех взаимозависимых вложенных циклов for
Фрагмент кода, который я должен проанализировать, приведен ниже: int sum = 0;
for (int i = 0; i
вопрос задан: 2 October 2012 19:47
0
ответов
расчет времени работы в наихудшем случае
Это из домашнего задания, но я прошу общий метод. Рассчитайте время выполнения следующего кода в наихудшем случае. целая сумма = 0; для (int i = 0; я *я < N; i++ )для (int j = 0; j < i *i; j++ )...
вопрос задан: 23 September 2012 16:55
0
ответов
докажите, что n = Big-O (1) с помощью индукции
Я знаю, что соотношение n = Big-O (1) неверно. Но если мы используем индукцию с участием Big-O, это можно доказать. Но заблуждение состоит в том, что мы не можем ввести Big-O. Но мой вопрос в том, как мы можем опровергнуть это отношение ...
вопрос задан: 19 September 2012 22:22
0
ответов
C Directed Graph Implementation Choice
Welcome mon amie, In some homework of mine, I feel the need to use the Graph ADT. However, I'd like to have it, how do I say, generic. That is to say, I want to store in it whatever I fancy. The ...
вопрос задан: 19 September 2012 16:29
0
ответов
Разыскивается :Рекуррентная формула In -Метод вывода двоичного дерева порядка
Я немного застрял в поисках формулы повторения этого java-метода void printInorder (Node v ){ if (v != null ){ printInorder (v. получитьлевый ()); System.out.println (v....
вопрос задан: 19 September 2012 16:27
0
ответов
Почему задача о рюкзаке псевдополиномиальна?
Я знаю, что Knapsack является NP-полным, в то время как он решается ДП. Они говорят, что решение DP является псевдополиномиальным, поскольку оно экспоненциально по «длине ввода» (то есть по количеству битов ...
вопрос задан: 19 September 2012 12:21
0
ответов
f (n) = n ^ log (n) полиномиальная или экспоненциальная сложность
Я пытаюсь выяснить, является ли f (n) = n ^ (logb (n)) находится в Theta (n ^ k) и поэтому растет полиномиально или в Theta (k ^ n) и, следовательно, растет экспоненциально. Сначала я попытался упростить функцию:
f (n) = n ^ (...
вопрос задан: 18 September 2012 16:58
0
ответов
Сложность реализации стека динамическим массивом
В типичной реализации динамического массива мы удваиваем стек, когда нет места для нового элемента. В этом случае удвоения среднее время операции push равно O (n). В чем сложность ...
вопрос задан: 16 September 2012 20:32
0
ответов
Существует ли теория, сочетающая теорию категорий/абстрактную алгебру и вычислительную сложность?
Теория категорий и абстрактная алгебра имеют дело с тем, как функции могут быть объединены с другими функциями. Теория сложности имеет дело с тем, насколько сложно вычислить функцию. Мне странно, что я не...
вопрос задан: 4 September 2012 21:50
0
ответов
Построение эффективных экземпляров монады в `Set` (и других контейнерах с ограничениями) с использованием монады продолжения
Set, подобно [], имеет совершенно определенные монадические операции. Проблема в том, что они требуют, чтобы значения удовлетворяли ограничению Ord, и поэтому невозможно определить return и > > = без ...
вопрос задан: 29 August 2012 17:49
0
ответов
Как доказать логарифмическую сложность
for (int i = 1; i
вопрос задан: 21 August 2012 09:37
0
ответов
Что означает O (M+N )?
Это основной вопрос... но я думаю, что O (M+N )совпадает с O (max (M,N )), так как больший член должен доминировать как мы идем в бесконечность? Кроме того, это будет отличаться от O (min (M,N ))тем, что...
вопрос задан: 13 August 2012 16:15
0
ответов
Сложность функции memset в C
Я обсуждал с друзьями фрагмент кода, и мы обсуждали использование функции memset в C, какой порядок в нотации Big -O для этой функции, если мы инициализируем массив размера N?
вопрос задан: 26 July 2012 06:02