0
ответов
Повторяемость T(n) = T(n^(1/2)) + 1
Я наблюдал за этой повторяемостью и хотел проверить, правильный ли подход я применяю. Т (п) = Т (п ^ (1/2)) + 1
= Т (п ^ (1/4)) + 1 + 1
= Т (п ^ (1/8)) + 1 + 1 + 1
...
= 1 + 1 + 1 + ... + 1 (всего ...
вопрос задан: 3 March 2012 22:32
0
ответов
Странные результаты при построении (Кормен) Вставка красно-черного дерева
Я реализовал красно-черные деревья в Python в соответствии с псевдокодом из книги Кормена «Введение в алгоритмы». Я хотел собственными глазами увидеть, что моя вставка действительно O (logn), поэтому я построил график времени ...
вопрос задан: 1 March 2012 23:23
0
ответов
Сложность двоичного поиска
Я смотрел онлайн-лекцию Berkley Uni и остановился на приведенном ниже.Проблема: Предположим, у вас есть коллекция CD, которая уже отсортирована. Вы хотите найти список компакт-дисков, название которых начинается с «...
вопрос задан: 27 February 2012 10:34
0
ответов
Разработка структуры данных, которая работает за время O (logn)
Я проверяю этот класс алгоритмов на предмет работы и пытаюсь решить некоторые практические задачи, заданные в классе. Эта проблема поставила меня в тупик, и я просто не могу понять ее. Ни одно из моих решений не пришло ...
вопрос задан: 21 February 2012 20:48
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
ответов
Временная сложность приведенного ниже кода
Я пытаюсь проверить временную сложность приведенной ниже простой программы.
Программа заменяет пробелы в строке на "% 20". Цикл для подсчета пробелов (время O (1)) foreach (char k in s) {...
вопрос задан: 12 February 2012 16:27
0
ответов
Сложность. Почему константы не имеют значения?
Кто-нибудь, пожалуйста, объясните мне, почему константы не имеют значения, когда речь идет о нотации большой буквы O? Почему сложность остается прежней при добавлении константы. Это не домашнее задание ...
вопрос задан: 2 February 2012 07:30
0
ответов
Каковы правила для «барьера Ω (n log n)» для алгоритмов сортировки?
Я написал простую программу, которая выполняет сортировку за O (n). Это очень неэффективно с памятью, но дело не в этом. Он использует принцип, лежащий в основе HashMap для сортировки: открытый класс NLogNBreak {public ...
вопрос задан: 31 January 2012 21:56
0
ответов
Как реализовать std :: make_heap при сравнении не более 3N?
Я посмотрел на стандарт C ++ 0x и обнаружил, что make_heap должен выполнять не более 3 * N сравнений. То есть Сформировать неупорядоченную коллекцию можно в O (N) / * @brief Construct ...
вопрос задан: 31 January 2012 21:55
0
ответов
Алгоритм, который проверяет, являются ли в массивах S и T целые числа s и t, поэтому s + t = k, если k задано число
. Я пытаюсь создать алгоритм, который принимает два массива: S и T из n целых чисел и целого числа k. Алгоритм проверяет, имеют ли массивы целые числа s и t, поэтому s + t = k. (S в S и t в T.) Алгоритм ...
вопрос задан: 29 January 2012 22:11
0
ответов
Эмпирическая оценка временной эффективности big-oh
Предыстория Я хотел бы оценить производительность big-oh некоторых методов в библиотеке с помощью бенчмарков. Мне не нужна точность - достаточно показать, что что-то является O(1), O(logn), O(n), O(nlogn), ...
вопрос задан: 12 January 2012 20:05
0
ответов
Почему время выполнения алгоритма выбора равно O (n)?
Согласно Википедии, время выполнения алгоритма выбора равно O (n), но меня это не убеждает. Может ли кто-нибудь объяснить, почему это O (n)? При обычной быстрой сортировке время выполнения составляет O (n log n). Каждый раз ...
вопрос задан: 9 January 2012 03:09
0
ответов
Как определить симплексную временную сложность (то есть максимальный поток)
Говорят, что симплексный алгоритм имеет экспоненциальную временную сложность наихудшего случая. Тем не менее, он все еще часто используется на практике. Как вы можете определить среднюю временную сложность для определенной задачи (решается ...
вопрос задан: 27 December 2011 23:57
0
ответов
Каково время выполнения shift/unshift в массиве ruby
Кто-нибудь знает, насколько эффективны shift и unshift в массиве ruby? Удаление из начала массива и необходимость перемещать каждый элемент в памяти может стать очень неэффективным. Я предполагаю, что ruby ...
вопрос задан: 2 December 2011 07:26
0
ответов
array_unique vs array_flip
Если бы у меня был массив целых чисел со знаком, например: Array
([0] => -3 [1] => 1 [2] => 2 [3] => 3 [4] => 3
) Чтобы получить уникальные значения, я бы инстинктивно использовал array_unique, но ...
вопрос задан: 1 December 2011 20:38
0
ответов
Обозначение Big Oh
Просто нужно быстрое подтверждение чего-нибудь. Если для выполнения алгоритму требуется n (n-1) / 2 тестов, неужели большое значение O (n ^ 2)?
вопрос задан: 24 November 2011 19:54
0
ответов
Анализ Big O с рекурсивным деревом сортировки Stooge
Я пытаюсь найти Big O для сортировки Stooge. Из Википедии алгоритм stoogesort (массив L, i = 0, j = length (L) -1), если L [j] 1, то ..
вопрос задан: 15 November 2011 02:30
0
ответов
логарифмическая сложность, представленная с помощью цикла?
, насколько я понял, линейная сложность может быть представлена как простой цикл, а квадратичная сложность может быть представлена как вложенный цикл. Как можно представить кубическую и логарифмическую сложность? Спасибо!
вопрос задан: 10 November 2011 16:43
0
ответов
Массивы нотаций Big O и вставки в связанные списки
Массивы нотаций Big O и вставки в связанные списки: согласно академической литературе для массивов это константа O (1), а для связанных списков - линейная O (n). Массив принимает только одно умножение и ...
вопрос задан: 14 October 2011 22:07
0
ответов
Каковы наиболее распространенные структуры данных и большой O для операций с ними?
Я пытаюсь разобраться в нотации Big O. Это кажется довольно абстрактным. Я выбрал наиболее распространенные структуры данных - массив, хэш, связанный список (одинарный и двойной) и двоичное дерево поиска и ...
вопрос задан: 14 October 2011 21:37
0
ответов
Big-O для шифрования с открытым ключом
Я искал несколько дней, но не могу найти алгоритм нотации Big-O для шифрования, дешифрования или попытки взломать зашифрованный файл (грубая сила ) с использованием открытого ключа ...
вопрос задан: 3 October 2011 20:45
0
ответов
Сколько раз будут выполняться вложенные циклы
Я пытаюсь понять, сколько раз в приведенном ниже коде выполняется инструкция «x = x + 1» как функция от «n»: for (i = 1; i <= n; i ++) for (j = 1; j <= i; j ++) for (k = 1; k <= j; k ++) ...
вопрос задан: 21 September 2011 13:30
0
ответов
Дополнительно: Как оптимизировать мой сложный алгоритм O (n²)
У меня есть данные о людях и местах в виде: Сущность Person имеет IList , каждая из которых имеет IList возможных мест Шаблон дня расписания, например. 10 дней доступно 4 недоступно ...
вопрос задан: 20 September 2011 16:50
0
ответов
Время прогона: Bounds vs Case
Примечание: Пожалуйста, не отмечайте это как домашнее задание! Я не студент и это не задание. Я инженер-программист, который убирает пыль с моего старого учебника "Структуры и алгоритмы данных" и пытается вспомнить ...
вопрос задан: 20 September 2011 11:17
0
ответов
Анализ Big-O с функциями внутри функций
Я не понимаю, как Big-O работает при работе с функциями внутри функций (при анализе наихудшего случая). Например, что, если у вас есть что-то вроде: for (int a = 0; a
вопрос задан: 19 September 2011 23:57
0
ответов
Возможно ли, что временная сложность любого алгоритма уменьшается с увеличением входного размера, любой пример
Я только что прочитал в алгоритмической книге Кормена, что big-O и big-omega не следуют свойству трихотомии. Это значит, что для двух функций, f(n) и g(n), может быть так, что ни f(n) = O(g(n)), ни f(...
вопрос задан: 17 September 2011 22:07
0
ответов
Время сложности операций Python Set?
Что такое временная сложность каждого из операций каждого из набора Python в большом обозначении? Я использую набор Python Type для операции на большом количестве предметов. Я хочу знать, как каждая операция ...
вопрос задан: 8 September 2011 16:38
0
ответов
Почему поиск таблиц так дешев?
Некоторое время назад я узнал немного о большой O-нотации и эффективности различных алгоритмов. Например, перебирать каждый элемент в массиве, чтобы что-то сделать с ним foreach(элементом в массиве)....
вопрос задан: 2 September 2011 18:49
0
ответов
Зависящие от пакета крючки импорта в Python
Я работаю над созданием модуля Python, который сопоставляет API, предоставляемый другим языком/инфраструктурой, с Python. В идеале, я бы хотел, чтобы это было представлено как единый корневой пакет, который разоблачает помощника...
вопрос задан: 1 September 2011 09:57