0
ответов
Существуют ли какие-либо реальные алгоритмы O (n ^ n)?
Существуют ли реальные алгоритмы со сложностью времени O (n ^ n), это не просто уловка? Я могу создать такой алгоритм, как вычисление n ^ n за O (n ^ n) / Θ (n ^ n): long n_to_the_power_of_m (int n, int m) {...
вопрос задан: 27 May 2011 18:22
0
ответов
Можно ли отсортировать n целых чисел с амортизированной сложностью O (n)?
Теоретически возможно ли отсортировать массив из n целых чисел с амортизированной сложностью O (n)? А как насчет попытки создать наихудший случай сложности O (n)? Большинство алгоритмов сегодня построены на ...
вопрос задан: 25 May 2011 08:56
0
ответов
Быстро взвешенный случайный выбор из очень большого набора значений
В настоящее время я работаю над проблемой, которая требует случайного выбора элемента из набора. Каждый из элементов имеет связанный с ним вес (вероятность выбора). Моя проблема в том, что для ...
вопрос задан: 19 May 2011 00:42
0
ответов
Определение сложности алгоритма целочисленной факторизации
Я начинаю изучать вычислительную сложность, нотацию BigOh и т.п., и мне было поручено выполнить алгоритм целочисленной факторизации и определить его сложность. Я написал алгоритм, и он ...
вопрос задан: 15 May 2011 01:19
0
ответов
What's the Time Complexity of Average Regex algorithms?
I'm not new to using regular expressions, and I understand the basic theory they're based on--finite state machines. I'm not so good at algorithmic analysis though and don't understand how a regex ...
вопрос задан: 5 May 2011 02:51
0
ответов
Временная сложность двух циклов for [дубликат]
Итак, я знаю, что временная сложность: for (i; i
вопрос задан: 3 May 2011 15:47
0
ответов
Что на самом деле означает Logn?
Я просто учусь в своем классе по алгоритмам и просматривал QuickSort. Я понимаю алгоритм и то, как он работает, но не знаю, как получить количество сравнений, которые он выполняет, или какой журнал ...
вопрос задан: 1 May 2011 10:06
0
ответов
Поиск «ребер узких мест» в графе
Для случайного однонаправленного графа я должен найти «ребра узких мест», чтобы добраться из одной вершины в другую. То, что я называю «ребра узкого места» (должно быть название получше!) - предположим, у меня есть ...
вопрос задан: 28 April 2011 20:12
0
ответов
Модульное тестирование равно и хэш-код - сложная история
У меня моральная дилемма. В моем приложении есть несколько объектов значений, которые неизменны и чрезвычайно просты. Я сгенерировал равенство и хэш-код с помощью IDE (intellij в моем случае), но выполняю ...
вопрос задан: 23 April 2011 13:57
0
ответов
Передача параметров потока Windows C ++
В Windows C ++ следующий поток создает поток : CreateThread (NULL, NULL, функция, параметр, NULL, & threadID); Это запустит "функцию" в новом потоке и передаст ему "параметр" как void * или ...
вопрос задан: 13 April 2011 18:57
0
ответов
Time/Space complexity of PHP Array
Is there a way or a resource for finding the time and space complexity of the Array implementation in PHP other than calculating it by hand? An array in PHP is actually an ordered map. A map is a ...
вопрос задан: 12 April 2011 20:12
0
ответов
Java: каково время объявления массива размером n?
Каково время объявления массива размера n в Java? Я полагаю, это будет зависеть от того, обнуляется ли память на сборке мусора (в этом случае это может быть O (1)) или на ...
вопрос задан: 12 April 2011 19:56
0
ответов
Быстрый алгоритм подсчета количества ациклических путей на ориентированном графе
Короче говоря, мне нужен быстрый алгоритм, чтобы подсчитать, сколько ациклические пути есть в простом ориентированном графе. Под простым графом я подразумеваю граф без петель и нескольких ребер.
Путь может начинаться с любого узла ...
вопрос задан: 6 April 2011 16:05
0
ответов
Как рассуждать о сложности пространства в Haskell
Я пытаюсь найти формальный способ подумать о сложности пространства в haskell. Я нашел эту статью о технике Graph Reduction (GR), которая мне кажется подходящей. Но у меня ...
вопрос задан: 5 April 2011 13:15
0
ответов
2 ^ n алгоритм сложности
Мне нужно реализовать и протестировать алгоритм со сложностью 2 ^ n. Я пытался найти один на некоторое время. Если есть какой-то способ, я могу добиться этого путем реализации - с точной сложностью 2 ^ ...
вопрос задан: 1 April 2011 02:00
0
ответов
Алгоритмическая сложность функции PHP strlen ()
Недавно меня спросили об этом вопрос на собеседовании, и я не знала, как на него ответить. Может ли кто-нибудь ответить на этот вопрос и описать его?
вопрос задан: 23 March 2011 05:36
0
ответов
Существуют ли какие-либо тесты, показывающие хорошую производительность `collections.deque`?
Меня всегда заинтриговал объект Python collections.deque. Это похоже на список, за исключением того, что добавление / удаление элементов в начале происходит быстрее, чем в списке. Это вызывает у меня желание заменить ...
вопрос задан: 19 March 2011 20:16
0
ответов
Найдите максимальную сумму интервалов в списке действительных чисел
Вот вопросы интервью, которые задал коллега позиция программирования. Я подумал, что это было здорово, чтобы посмотреть, как интервьюируемый обдумывает это. Я хотел бы получить ответы о том, как SO ...
вопрос задан: 16 March 2011 20:04
0
ответов
Изучение эффективных алгоритмов
До сих пор я в основном концентрировался на том, как правильно спроектировать код, сделать его как можно более читабельным и обслуживаемым, насколько это возможно. Поэтому я всегда решил узнать подробности о более высоком уровне ...
вопрос задан: 12 March 2011 14:05
0
ответов
анализ временной сложности моих программ
У меня проблема с определением временной сложности алгоритмов. for (int i = 0; i
вопрос задан: 11 March 2011 06:30
0
ответов
Какова временная сложность упорядоченных операций в TreeSet?
Какова временная сложность следующих операций в java.util.TreeSet? первый()
последний()
нижний ()
superior () Я бы предположил, что это постоянное время, но API не дает никаких гарантий.
вопрос задан: 7 March 2011 01:14
0
ответов
Сложность быстрой сортировки, когда все элементы одинаковы?
У меня есть массив из N одинаковых чисел. Я применяю к нему быструю сортировку.
Какой должна быть временная сложность сортировки в этом случае. Я задумался над этим вопросом, но не получил точного ответа ...
вопрос задан: 26 February 2011 12:23
0
ответов
Слияние отсортированных массивов, какова оптимальная временная сложность?
У меня есть m массивов, каждый массив имеет длину n. Каждый массив отсортирован. Я хочу создать единый массив длиной m * n, содержащий все отсортированные значения предыдущих массивов (включая повторяющиеся значения). ...
вопрос задан: 25 February 2011 10:20
0
ответов
Почему длина списка уменьшается до sqrt (n) после каждого сравнения в поиске с интерполяцией?
Согласно книге, которую я читаю, поиск по интерполяции в среднем принимает O (loglogn).
В книге предполагается, что каждое сравнение сокращает длину списка с n до sqrt (n). Что ж, это несложно ...
вопрос задан: 5 February 2011 03:10
0
ответов
Избегайте сложности O (n ^ 2) для обнаружения столкновений
Я разрабатываю простую 2D-игру на основе тайлов. У меня есть уровень, заполненный объектами, которые могут взаимодействовать с плитками и друг с другом. Проверить столкновение с тайловой картой довольно просто, и это может ...
вопрос задан: 4 February 2011 09:13
0
ответов
Что? Какова асимптотическая сложность операции GroupBy?
Меня интересует асимптотическая сложность (большой O) операции GroupBy для неиндексированных наборов данных. Какова сложность самого известного алгоритма и какова сложность алгоритмов, использующих SQL ...
вопрос задан: 3 February 2011 18:33
0
ответов
Complexity of algorithms of different programming paradigms
I know that most programming languages are Turing complete, but I wonder whether a problem can be resolved with an algorithm of the same complexity with any programming language (and in particular ...
вопрос задан: 25 January 2011 19:02
0
ответов
Почему сортировка нитей O (n sqrt n) в среднем случае?
Я считаю, что сортировка цепочек очень удобна для сортировки односвязных списков в постоянном пространстве, потому что она намного быстрее, чем, например, сортировка вставкой. Я понимаю, почему в лучшем случае это O (n) (список уже ...
вопрос задан: 3 January 2011 19:50
0
ответов
Сложность получения / размещения HashMap
Мы привыкли говорить, что операции получения / размещения HashMap являются O (1). Однако это зависит от реализации хэша. Хэш объекта по умолчанию - это внутренний адрес в куче JVM. Уверены ли мы, что это ...
вопрос задан: 29 December 2010 11:40
0
ответов
(Dis) Доказательство того, что один алгоритм работает быстрее, чем другой из-за внутренних особенностей языка
. Для проекта в университете нам пришлось реализовать несколько различных алгоритмов для вычисления классов эквивалентности, когда задан набор элементов и набор отношений между упомянутыми элементами . Мы ...
вопрос задан: 20 December 2010 00:41