0
ответов
Почему пузырьковая сортировка O (n^2 )?
интервал текущий мининдекс = 0; для (int front = 0; фронт < intArray.length; фронт++ ){ текущийМинИндекс = передний; для (int i = передний; я < intArray.length; i++ ){ if (intArray[i] &...
вопрос задан: 13 July 2012 20:29
0
ответов
Какова сложность (Big -O )этого алгоритма?
Я достаточно хорошо знаком с алгоритмическим анализом и могу сказать большое -О о большинстве алгоритмов, с которыми работаю. Но я застрял в течение нескольких часов, не в силах придумать Большой -O для этого кода, который я пишу. В основном это'...
вопрос задан: 11 July 2012 19:29
0
ответов
Что такое большая O функции Oracle MAX?
Является ли временная сложность функции Oracle MAX O (1 ), O (log n )или O (n )по отношению к количеству строк в таблице?
вопрос задан: 28 June 2012 17:11
0
ответов
Какова сложность std::vector::clear(), когда T — примитивный тип?
Насколько я понимаю, сложность операции clear() прямо пропорциональна размеру контейнера, потому что должны быть вызваны деструкторы. Но как насчет примитивных типов (и POD)? Это кажется лучшим...
вопрос задан: 27 June 2012 23:03
0
ответов
Как обратные ссылки в регулярных выражениях требуют обратного отслеживания?
Я читал http://swtch.com/~rsc/regexp/regexp1.html, и в нем автор говорит, что для того, чтобы иметь обратные ссылки в регулярных выражениях, нужно выполнять поиск с возвратом при сопоставлении, и это делает наихудший случай. ..
вопрос задан: 19 June 2012 15:25
0
ответов
Почему алгоритмы «разделяй и властвуй» часто работают быстрее, чем грубая сила?
Почему алгоритмы «разделяй и властвуй» часто работают быстрее, чем грубая сила? Например, чтобы найти ближайшую пару точек. Я знаю, что вы можете показать мне математическое доказательство. Но интуитивно, почему это...
вопрос задан: 15 June 2012 00:54
0
ответов
Временная сложность объединения двух отсортированных массивов размера n и m
Мне просто интересно, какова временная сложность объединения двух отсортированных массивов размера n и m, учитывая, что n всегда больше m. Я думал об использовании сортировки слиянием, которую я предполагаю в этом случае...
вопрос задан: 14 June 2012 18:31
0
ответов
найти все прямоугольные области с определенными свойствами в матрице
с учетом матрицы n*m с возможными значениями 1, 2 и нуля: . . . . . 1 . . . 1 . . . . . 1 . . . 2 . . . . . . . . 2 . . . 1 . . . . . 1 . . . . . . . . . . . 1 . . 2 . . 2 . . . ....
вопрос задан: 12 June 2012 18:23
0
ответов
Что такое временная сложность A* и как она получается?
Мне было интересно, может ли кто-нибудь объяснить временную сложность A*.
Я использую эвристику, которая использует евклидово расстояние для оценки веса. В эвристической функции нет циклов.
Итак, я...
вопрос задан: 14 May 2012 18:02
0
ответов
Сколько сравнений будет выполнять бинарный поиск в худшем случае с использованием этого алгоритма?
Здравствуйте, ниже приведен псевдокод для моей реализации бинарного поиска: Вход: (A[0...n-1], K)
начало l ← 0; r ← n-1 в то время как l ≤ r do m ← floor((l+r)/2) если K > A[m], то l ← m+1 ...
вопрос задан: 13 May 2012 11:58
0
ответов
Структура данных для поиска и обновления O(log N) с учетом небольшого размера кэша L1
В настоящее время я работаю над проектом встроенного устройства, где у меня возникают проблемы с производительностью. . Профилирование обнаружило операцию O(N), которую я хотел бы исключить. В основном у меня есть два массива int A[...
вопрос задан: 11 May 2012 13:33
0
ответов
Оптимизируют ли компиляторы C и C++ сравнения с функцией звонки?
Оптимизируют ли обычно компиляторы C и C++ сравнения с функциями? Например, на этой странице предполагается, что функция size в std::lists в C++ может иметь линейную сложность O(N) в некоторых стандартах...
вопрос задан: 11 May 2012 12:32
0
ответов
«K-преобразованные» перестановки
Я бился головой об этой проблеме в течение нескольких дней и тщательно искал в Интернете какие-либо подсказки о том, как ее решить. Если вам нравятся математически ориентированные задачи программирования, пожалуйста, возьмите ...
вопрос задан: 9 May 2012 23:23
0
ответов
Насколько дорого обходится сравнение двух неупорядоченных наборов на равенство?
Имея два стандартных::набора, можно просто перебирать оба набора одновременно и сравнивать элементы, что приводит к линейной сложности. Это не работает для std::unordered_sets, потому что элементы...
вопрос задан: 12 April 2012 06:33
0
ответов
Почему SortedSet.GetViewBetween не равно O(log N)?
В .NET 4.0+ класс SortedSet имеет метод GetViewBetween(l, r), который возвращает представление интерфейса в части дерева, содержащее все значения между двумя указанными. Учитывая, что...
вопрос задан: 28 March 2012 21:03
0
ответов
Какова временная и пространственная сложность алгоритма FP-Growth?
Как рассчитать временную и пространственную сложность алгоритма FP_growth в интеллектуальном анализе данных??
вопрос задан: 26 March 2012 12:58
0
ответов
Какова сложность времени поиска HashSet(IEqualityComparer)?
В C#.NET мне нравится использовать HashSet из-за их предполагаемой временной сложности O(1) для поиска. Если у меня есть большой набор данных, которые будут запрашиваться, я часто предпочитаю использовать HashSet вместо List, поскольку...
вопрос задан: 21 March 2012 20:05
0
ответов
Стабильная сортировка сравнением с O(n *log(n))времени и O(1)пространственной сложностью
Просматривая список алгоритмов сортировки в Википедии, я заметил, что есть нет стабильной сортировки сравнением, которая имеет O(n*log(n))(наихудший-случай)время-сложность и O(1)(наихудший-случай)пространство-сложность....
вопрос задан: 19 March 2012 20:37
0
ответов
Гибрид быстрой сортировки и сортировки вставками ожидаемое время работы
Я занимаюсь самостоятельным изучением 3-го издания CLRS, и вот один из самых сложных вопросов, с которыми я столкнулся, а также его ответ как услуга для всех. 7.4-5
Мы можем улучшить время выполнения быстрой сортировки в...
вопрос задан: 7 March 2012 06:19
0
ответов
Сложность двоичного поиска
Я смотрел онлайн-лекцию Berkley Uni и остановился на приведенном ниже.Проблема: Предположим, у вас есть коллекция CD, которая уже отсортирована. Вы хотите найти список компакт-дисков, название которых начинается с «...
вопрос задан: 27 February 2012 10:34
0
ответов
Сублинейный, но простой алгоритм Dynamic Convex Hull?
Мне нужно решить проблему алгоритма динамической выпуклой оболочки, то есть поддерживать выпуклую оболочку двумерных точек, где я могу добавлять и удалять точки. Наивный подход явно O (N); всякий раз, когда один из N ...
вопрос задан: 23 February 2012 09:26
0
ответов
Быстрая проверка, является ли набор надмножеством сохраненных наборов
Проблема. Мне дано N массивов логических значений C. Я хочу организовать их в структуру данных, которая позволяет мне выполнять следующую операцию как можно быстрее: Учитывая новый массив, вернуть истину, если это ...
вопрос задан: 21 February 2012 00:37
0
ответов
Почему алгоритм медианы медианы не может использовать размер блока 3 ?
Я работаю над анализом детерминированных медианных результатов в предположении, что входные данные делятся на 3 части, а не на 5, и вопрос в том, где они разрушаются? the ...
вопрос задан: 20 February 2012 14:38
0
ответов
Большой O, какова сложность суммирования серии из n чисел?
Я всегда думал, что сложность: 1 + 2 + 3 + ... + n равна O (n), а сложение двух n по n матриц будет O (n ^ 2). Но сегодня я прочитал из учебника: «По формуле суммы первых n ...
вопрос задан: 12 February 2012 21:34
0
ответов
Всегда ли O (log n) быстрее, чем O (n)
Если есть 2 алгоритма, которые вычисляют один и тот же результат с разной сложностью, всегда ли O (log n) будет быстрее? Если да, то объясните. Кстати, это не вопрос о назначении.
вопрос задан: 8 February 2012 20:55
0
ответов
Haskell GHC: какова временная сложность сопоставления с образцом с N конструкторами?
Допустим, у нас есть следующий Haskell: data T = T0 | T1 | T2 | ... | TN toInt: : T -> Int
toInt t = case t of T0 -> 0 T1 -> 1 T2 -> 2 ... TN -> N Какой алгоритм используется ...
вопрос задан: 27 January 2012 00:12
0
ответов
Пояснение к заявлению о производительности двоичного поиска в коллекции из javadoc
Я не понимаю, как анализировать производительность binarySearch из коллекций. В нем говорится: Если указанный список не реализует интерфейс RandomAccess и является большим, этот метод подойдет. ...
вопрос задан: 24 January 2012 20:23
0
ответов
Практическая вычислительная сложность c ++ для SQRT ()
Какая разница в циклах ЦП (или, по сути, в «скорости») между x / = y; и #include x = sqrt (y); EDIT: я знаю, что операции не эквивалентны, я просто произвольно ...
вопрос задан: 16 January 2012 19:55
0
ответов
Сложность оператора равенства F #
У меня вопрос об операторе «=» (равно) по умолчанию в F #. Это позволяет сравнивать пользовательские типы объединений. Возникает вопрос: в чем это сложность? Например, рассмотрим следующий тип: ...
вопрос задан: 16 January 2012 18:34
0
ответов
Какую структуру данных лучше всего использовать для запросов на основе типов?
Я нахожусь в процессе создания игры, и в этом процессе я столкнулся с небольшой проблемой. У меня много разных типов игровых элементов. Все они относятся к типу Entity. Есть много типов ...
вопрос задан: 29 December 2011 03:15