Лучшие big-o вопросы ИТ разработчиков

  • 29 голосов
  • 3 ответа
  • 0 просмотров
3 ответа

Биг О нотация Log Base 2 или Log Base 10 [копия]

На этот вопрос уже есть ответ здесь: Является ли журнал Big O (logn) базой e? [/questions/1569702/is-big-ologn-log-base-e] 7 ответовКогда в статьях / вопросах указывается, что время выполнения алгоритма Big O равно O (LogN). Например, Quicksort ...

Задан 20 Dec 2013, 17:50 от Computernerd
  • 29 голосов
  • 0 ответов
  • 0 просмотров
0 ответов

Если мы используем многобуквенные слова, нам придется реже находить конец StringBuffer, что приведет к сокращению времени процессора и «лучшему» падежу.

авляю этот текст из моей книги. Это говорит о сложности, если O (n2) и также дает объяснение этому, но я не вижу, как. Вопрос: Каково время выполнения этого кода? public String makeSentence(String[] words) { StringBuffer sentence = ...

Задан 23 Aug 2011, 04:01 от Someone
  • 1 голос
  • 3 ответа
  • 0 просмотров
3 ответа

Временная сложность двойных петель

Меня несколько смущают следующие алгоритмы. В частности, я не понимаю, почему первым является O (n), а вторым - O (n ^ 2). Возможно, моя единственная интуиция заключается в том, что внутренние и внешние циклы для первого алгоритма не «связаны». ...

Задан 04 Feb 2014, 17:36 от codeMonkey17
  • 6 голосов
  • 2 ответа
  • 0 просмотров
2 ответа

Сложность бинарного поиска

Я смотрю онлайн-лекцию Berkley Uni и застрял ниже. проблемаПредположим, у вас есть коллекция компакт-дисков, которые уже отсортированы. Вы хотите найти список компакт-дисков, название которых начинается с «Best Of». Решение: Мы будем ...

Задан 27 Feb 2012, 02:58 от tabiul
  • 21 голос
  • ответ
  • 0 просмотров
ответ

Это не средний анализ случая. Для анализа среднего случая необходимо учитывать все возможные варианты поворота, а не только ожидаемое значение элемента поворота.

едия утверждает, что среднее время выполнения алгоритма быстрого выбора (Ссылка [http://en.wikipedia.org/wiki/Selection_algorithm#Partition-based_general_selection_algorithm] ) является O (n). Однако я не мог четко понять, как это так. Может ли ...

Задан 10 May 2011, 04:35 от Ravi
  • 8 голосов
  • 0 ответов
  • 0 просмотров
0 ответов

Почему алгоритм среднего значения медиан не может использовать размер блока 3?

Я работаю с анализом детерминированных медианных результатов в предположении, что вход делится на 3 части, а не на 5, и вопрос в том, где он ломается? детерминированный медианный алгоритм поиска: SELECT (i, n) Разделите n элементов на группы ...

Задан 01 Feb 2012, 03:31 от Lara
  • 14 голосов
  • 5 ответов
  • 0 просмотров
5 ответов

Какова временная сложность LinkedList.getLast () в Java?

У меня есть собственный LinkedList в классе Java, и мне часто нужно будет извлечь последний элемент в списке. Списки нужно масштабировать, поэтому я пытаюсь ...

Задан 04 May 2010, 13:37 от Mark McDonald
  • 72 голосов
  • 12 ответов
  • 0 просмотров
12 ответов

Код

лкивался с этим вопросом:Реализуйте очередь, в которой push_rear (), pop_front () и get_min () - все операции с постоянным временем. Сначала я думал об использовании структуры данных с минимальной кучей, которая имеет сложность O (1) для get_min ...

Задан 26 Jan 2011, 06:54 от bits
  • 3 голосов
  • 3 ответа
  • 0 просмотров
3 ответа

Я не думаю, что это правильно, но я хочу, чтобы мне сказали, почему я не прав. Смотри мой ответ.

я есть теоретический вопрос, буду признателен, если вы сообщите мне здесь. Скажем, у нас есть эти две части кода. Первый: For Each cell In rng1 collectionOfValues.Add (cell.Value) Next For Each cell In rng2 collectionOfAddresses.Add ...

Задан 28 Jan 2011, 12:00 от tube-builder
  • 4 голосов
  • 0 ответов
  • 0 просмотров
0 ответов

сложность для вложенных циклов

Я пытаюсь выяснить сложность цикла for, используя обозначение Big O. Я делал это раньше в других своих классах, но этот более строгий, чем другие, потому что он на самом алгоритме. Код выглядит следующим образом: for(i=n ; i>1 ; i/=2) //for any ...

Задан 24 May 2013, 20:45 от Hassan Bendouj
  • 12 голосов
  • 4 ответа
  • 0 просмотров
4 ответа

Big-Oh - это показатель того, как требуемые ресурсы масштабируются по мере увеличения N. O (5 часов) и O (5 секунд) - это O (1), поскольку при увеличении N никаких дополнительных ресурсов не требуется.

ыстро подумать; Можно ли утверждать, что O (∞) на самом деле является O (1)? Я имею в виду, это не зависит от размера ввода?Так что в некотором смысле это, постоянный, хотя это бесконечность.Или это единственный «правильный» способ выразить это ...

Задан 11 Apr 2011, 20:48 от Poul Walker
  • 3 голосов
  • 2 ответа
  • 0 просмотров
2 ответа

Теорема магистра с f (n) = log n

Для теоремы магистраT(n) = a*T(n/b) + f(n) Я использую 3 случая: Еслиa*f(n/b) = c*f(n) для некоторой константыc > 1 тогдаT(n) = (n^log(b) a)Еслиa*f(n/b) = f(n) тогдаT(n) = (f(n) log(b) n)Еслиa*f(n/b) = c*f(n) для некоторой константыc < 1 ...

Задан 31 Mar 2013, 23:04 от amir shadaab
  • 65 голосов
  • 2 ответа
  • 0 просмотров
2 ответа

мультимножество, сложность карты и хеш-карты

Я хотел бы знать сложность обозначений Big O для классов мультимножеств STL, map и hash map, когда:вставка записейдоступ к записямизвлечение записейсравнение...

Задан 21 Oct 2008, 17:02 от Harry
  • 7 голосов
  • 5 ответов
  • 0 просмотров
5 ответов

Big Oh Notation - формальное определение

Я сейчас читаю учебник для моего класса Java III. Мы читаем о Big-Oh, и меня немного смущает его формальное определение.Формальное определение: «Функция f (n...

Задан 02 May 2010, 19:50 от ShrimpCrackers
  • 0 голосов
  • 0 ответов
  • 0 просмотров
0 ответов

Но мой коллега уверен, что сложность O (n ^ 5). Но я не могу понять, почему. Не могли бы вы описать, почему он говорит O (n ^ 5).

for i in xrange(1,n+1): for j in xrange(1,i*i): if j%i==0: for k in xrange(0,j): print("*")а будет временная сложность вышеуказанного алгоритма?

Задан 04 Oct 2017, 10:27 от Abhishek Khandelwal
  • 0 голосов
  • 4 ответа
  • 0 просмотров
4 ответа

O (N²)

от вопрос уже есть ответ здесь:Как найти временную сложность алгоритма 9 ответовможет кто-нибудь сказать мне, какова временная сложность этого алгоритма? име...

Задан 20 May 2017, 12:25 от Ben
  • 6 голосов
  • 3 ответа
  • 0 просмотров
3 ответа

Спасибо за ответ. На самом деле не пытался сравнить 2, а скорее изучал детали обоих.

Mozilla четко описываетhasOwnProperty() [https://developer.mozilla.org/en/JavaScript/Reference/Global_Objects/Object/hasOwnProperty] иin [https://developer.mozilla.org/en/JavaScript/Reference/Operators/Special/in] оператор. Тем не менее, он не ...

Задан 16 May 2011, 00:31 от haknick
  • 24 голосов
  • 8 ответов
  • 0 просмотров
8 ответов

Большой О, какова сложность суммирования серии из n чисел?

Я всегда думал о сложности: 1 + 2 + 3 + ... + n является O (n), и суммирование двух n по n матриц будет O (n ^ 2). Но сегодня я прочитал из учебника: «по формуле для суммы первых n целых чисел это n (n + 1) / 2», а затем так: (1/2) n ^ 2 + ...

Задан 12 Feb 2012, 21:34 от user1032613
  • 48 голосов
  • 7 ответов
  • 0 просмотров
7 ответов

Различия между временной сложностью и пространственной сложностью?

Я видел, что в большинстве случаев временная сложность связана с пространственной сложностью и наоборот. Например, в обход массива:

Задан 08 Sep 2013, 14:41 от Little
  • 15 голосов
  • 5 ответов
  • 0 просмотров
5 ответов

Реализация Regex, которая может обрабатывать сгенерированные компьютером регулярные выражения: * non-backtracking *, O (n)?

Edit 2: Для практической демонстрации того, почему это остается важным, смотрите не дальше, чемСобственное отключение, вызванное регулярным выражением, в sta...

Задан 20 Jul 2016, 20:22 от 15 revsEamon Nerbonne
  • 1 голос
  • 3 ответа
  • 0 просмотров
3 ответа

Время вычисления T (n) и Big-O с бесконечным циклом

Я запутался в том, как создать функцию T (n) для измерения времени вычислений для вложенного бесконечного цикла. Вот код: x=1; for(int i = 0;i<n-1;i++){ for(int j = 1; j<=x; j++){ cout << j << endl; x*=2; } }Таким образом, внутренний цикл будет ...

Задан 11 Oct 2011, 22:40 от whittenc
  • 7 голосов
  • 3 ответа
  • 0 просмотров
3 ответа

если вы будете следовать этому, вы можете получить любую сложную функцию.

, являетсяf = O(g)У меня трудно разобраться с вышеуказанным вопросом. Пример будет приветствоваться. Кроме того, если вы используете правило l'Hôpital, пожалуйста, покажите, как вы делаете дифференцирование.e^f = O(e^g)? Если вы Googling, то вы ...

Задан 08 Mar 2011, 17:03 от Programmer
  • 26 голосов
  • 3 ответа
  • 0 просмотров
3 ответа

Правильные ответы - это то, что отмечает Джон Скит.

дполагал, что LinkedList.Clear () был O (1) для проекта, над которым я работаю, так как я использовал LinkedList, чтобы истощить BlockingQueue у моего потребителя, который нуждается в высокой пропускной способности, очищая и повторно используя ...

Задан 01 Mar 2011, 22:12 от Leri
  • 3 голосов
  • 4 ответа
  • 0 просмотров
4 ответа

Сложность поиска всех простых путей с использованием поиска в глубину?

Спасибо всем, кто отвечает идеями и альтернативными решениями. Всегда приветствуются более эффективные способы решения проблем, а также напоминания о моих предположениях. Тем не менее, я бы хотел, чтобы вы на мгновение проигнорировали проблему, ...

Задан 02 Dec 2009, 04:12 от hexium
  • 15 голосов
  • 0 ответов
  • 0 просмотров
0 ответов

Сложность факториального рекурсивного алгоритма

Сегодня в классе мой учитель написал на доске этот рекурсивный факториальный алгоритм: int factorial(int n) { if (n == 1) return 1; else return n * factorial(n-1); } Она сказала, что это имеет стоимостьT(n-1) + 1. Затем с помощью итерационного ...

Задан 04 May 2013, 10:05 от Francesco Bonizzi
  • 8 голосов
  • 4 ответа
  • 0 просмотров
4 ответа

Что это означает, когда операция «приближается к O (1)», а не «является O (1)»?

Рассмотрим, например, документацию для .NET Framework 4.5.Dictionary<TKey, TValue> класс: взамечания [http://msdn.microsoft.com/en-us/library/kw5aaea4%28v=vs.110%29.aspx] для.ContainsKey метод, они утверждают, что Этот метод приближается к ...

Задан 14 Nov 2013, 21:46 от David S.
  • 2 голосов
  • 0 ответов
  • 0 просмотров
0 ответов

Получить количество элементов в отсортированном массиве, попадающих в определенный диапазон за время log (n)

Скажем, у меня есть массив следующего класса, отсортированный в порядке возрастания по y: public class Obj { public int x; public int y; }Как я могу найти количество элементов Obj в массиве, у которых есть значения y в пределах минимального ...

Задан 06 Mar 2013, 09:01 от Jack
  • 37 голосов
  • 0 ответов
  • 0 просмотров
0 ответов

Словарь ключей Python. «В» сложность

Быстрый вопрос, чтобы в основном удовлетворить мое любопытство по теме. Я пишу несколько больших программ на Python с базой данных SQlite и буду иметь дело с большим количеством записей в будущем, поэтому мне нужно оптимизировать как можно ...

Задан 09 Jul 2013, 03:25 от tknickman
  • 1 голос
  • 0 ответов
  • 0 просмотров
0 ответов

Противоречие в Cormen относительно вида вставки

В теореме Кормена 3.1 говорится, что Например,лучший случайвремя работысортировка вставокявляетсябольшой-омега (п), в то время какхудший случайвремя работыВид вставкиявляетсяBig-ой (п ^ 2), Время выполнения сортировки вставки поэтому находится ...

Задан 03 Jul 2013, 20:57 от Akshay Jindal
  • 8 голосов
  • 1 ответ
  • 0 просмотров
1 ответ

Доказательство и опровержение BigO

При доказательстве и опровержении вопросов Большого О, в которых прямо говорится, что для подтверждения и опровержения используется определение, у меня возни...

Задан 11 Feb 2010, 21:50 от Faisal Abid
  • 22 голосов
  • 0 ответов
  • 0 просмотров
0 ответов

Когда запись Big-O терпит неудачу?

На каких примерах нотация Big-O [1] не работает на практике? То есть, когда время выполнения алгоритмов Big-O предсказывает алгоритм A быстрее, чем алгоритм B, но на практике алгоритм B быстрее при его запуске? Чуть шире: когда теоретические ...

Задан 02 Jun 2009, 18:57 от Jonas Kölker
Page 1 of 5
1 2 3 4 5