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

  • 42голосов
  • 6ответов
  • 0просмотров

Разница между O (n) и O (log (n)) - что лучше и чем конкретно является O (log (n))?

Это мой первый курс по структурам данных и каждой лекции / ТА лекции, о которых мы говоримO(log(n)) , Это, вероятно, глупый вопрос, но я был бы признателен, если бы кто-нибудь смог мне объяснить, что именно это означает!

ЗаданJan 17, 2013, 8:16 PMотnhahtdhron
  • 40голосов
  • 4ответа
  • 0просмотров

Интуитивно понятное объяснение, почему QuickSort это n log n?

Кто-нибудь может дать «простой английский»? Интуитивно понятное, но формальное объяснение того, что делает QuickSort n log n? Насколько я понимаю, он должен пройти через n элементов, и он делает этот журнал n раз ... Я не уверен, как выразить это ...

ЗаданMay 03, 2012, 5:16 AMотJim_CS
  • 19голосов
  • 3ответа
  • 0просмотров

Структуру данных для O (log N) найти и обновить, учитывая небольшой кэш L1

В настоящее время я работаю над проектом встраиваемого устройства, в котором у меня проблемы с производительностью. Профилирование обнаружило операцию O (N), которую я хотел бы устранить. У меня в основном два массиваint A[N] а такжеshort B[N], ...

ЗаданMay 11, 2012, 1:33 PMотMSalters
  • 17голосов
  • 3ответа
  • 0просмотров

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

Привет там ниже псевдокод для моей реализации двоичного поиска: Input: (A[0...n-1], K) begin l ← 0; r ← n-1 while l ≤ r do m ← floor((l+r)/2) if K > A[m] then l ← m+1 else if K < A[m] then r ← m-1 else return m end if end while return -1 // key ...

ЗаданMay 13, 2012, 11:58 AMотHarry Tiron
  • 5голосов
  • 2ответа
  • 0просмотров

Временная сложность объединения двух отсортированных массивов размером n и m

Мне просто интересно, какова временная сложность объединения двух отсортированных массивов размера n и m, учитывая, чтоn is always greater than m. Я думал об использовании сортировки слиянием, которая, как я полагаю, в этом случае будет ...

ЗаданJun 14, 2012, 6:31 PMотdnawab
  • 25голосов
  • 14ответов
  • 0просмотров

Применяли ли вы теорию вычислительной сложности в реальной жизни?

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

ЗаданSep 26, 2008, 4:24 PMотDimaMartin08
  • 53голосов
  • 6ответов
  • 0просмотров

Событие выхода из консольного приложения .NET

Есть ли в .NET метод, например событие, для определения момента выхода из консольного приложения? Мне нужно очистить некоторые потоки и COM-объекты. Я запускаю цикл сообщений без формы из консольного приложения. Компонент DCOM, который я ...

ЗаданJul 03, 2015, 5:28 PMотSammuelMirandauser79755
  • 14голосов
  • 2ответа
  • 0просмотров

Какова сложность std :: vector <T> :: clear (), когда T является примитивным типом?

Я понимаю, что сложность операции clear () линейна по размеру контейнера, потому что должны вызываться деструкторы. Но как насчет примитивных типов (и POD)? Кажется, лучше всего было бы установить размер вектора равным 0, чтобы сложность была ...

ЗаданJun 27, 2012, 11:03 PMотuser1487088
  • 53голосов
  • 5ответов
  • 0просмотров

временная сложность unshift () и push () в Javascript

Я знаю, в чем разница между методами unshift () и push () в Javascript, но мне интересно, какова разница во временной сложности? Я полагаю, что для метода push () используется O (1), потому что вы просто добавляете элемент в конец массива, но я ...

ЗаданSep 03, 2012, 3:35 PMотJames McLaughlindperitch
  • 5голос
  • 1ответ
  • 0просмотров

Количество сравнений в Merge-Sort

Я изучал тему сортировки слиянием, с которой столкнулся с такой концепцией, как число сравнений в сортировке слиянием (в худшем случае и согласноВикипедия [http://en.wikipedia.org/wiki/Merge_sort]) равно (n & # x2308; lg n & # x2309; - 2⌈lg n⌉ + ...

ЗаданSep 10, 2012, 8:12 AMотMvGShahin
  • 11голосов
  • 5ответов
  • 0просмотров

Сложность для башен Ханоя?

Недавно я решал проблему Ханойских Башен. Я использовал «Разделяй и властвуй» Стратегия для решения этой проблемы. Я разделил основную проблему на три более мелкие подзадачи, и, таким образом, возникла следующая повторяемость. > ...

ЗаданSep 12, 2012, 7:21 AMот
  • 16голосов
  • 11ответов
  • 0просмотров

Используете ли вы оценку сложности Big-O в «реальном мире»?

Недавно в одном из интервью мне было задано несколько вопросов, связанных с Big-O различных алгоритмов, которые возникли в ходе технических вопросов. Я не думаю, что у меня это хорошо получилось ... За десять лет, прошедших с тех пор, как я ...

ЗаданJun 07, 2012, 6:47 PMот2 revs, 2 users 100%beggs
  • 25голосов
  • 3ответа
  • 0просмотров

Очередь приоритетов убирает время сложности

Какова сложность (биг-о-о) дляremove() функция в классе очереди приоритетов в Java? Я нигде не могу найти ничего задокументированного, я думаю, что это O (n), учитывая, что вы должны найти элемент, прежде чем удалить его, а затем переставить ...

ЗаданOct 04, 2012, 1:08 AMотsamturner
  • 53голосов
  • 5ответов
  • 0просмотров

временная сложность unshift () и push () в Javascript

Я знаю, в чем разница между методами unshift () и push () в Javascript, но яМне интересно, в чем разница во времени сложности? Я полагаю, для метода push () O (1), потому что вы 'просто добавить элемент в конец массива, но яя не уверен в методе ...

ЗаданSep 03, 2012, 1:33 PMотdperitch
  • 5голос
  • 1ответ
  • 0просмотров

Количество сравнений в Merge-Sort

Я изучал тему сортировки слиянием, с которой столкнулся с такой концепцией, как число сравнений в сортировке слиянием (в худшем случае и согласноВикипедия [http://en.wikipedia.org/wiki/Merge_sort]) равно (n ⌈LG N⌉ - 2⌈LG N⌉ + 1); на самом деле ...

ЗаданSep 10, 2012, 3:59 AMотShahin
  • 11голосов
  • 5ответов
  • 0просмотров

Сложность для башен Ханоя?

Недавно я решал проблему Ханойских Башен. Я использовал "Разделяй и властвуй " Стратегия для решения этой проблемы. Я разделил основную проблему на три более мелкие подзадачи, и, таким образом, возникла следующая повторяемость. > Т (п) = 2T ...

ЗаданSep 12, 2012, 5:21 AMотuser1581106
  • 25голосов
  • 3ответа
  • 0просмотров

Очередь приоритетов убирает время сложности

Какова сложность (биг-о-о) дляremove() функция в классе очереди приоритетов в Java? Я могу'Я не думаю, что что-нибудь было документированоs O (n), учитывая, что вы должны найти элемент, прежде чем удалить его, а затем переставить дерево. но ...

ЗаданOct 03, 2012, 11:08 PMотsamturner
  • 55голосов
  • 9ответов
  • 0просмотров

Hashtable в C ++?

Я обычно использую C ++ stdlib map всякий раз, когда мне нужно сохранить некоторые данные, связанные с определенным типом значения (значение ключа - например, строка или другой объект). Реализация карты stdlib основана на деревьях, которые ...

ЗаданSep 25, 2008, 12:11 PMотMarcos Bento
  • 197голосов
  • 3ответа
  • 0просмотров

Определение сложности для рекурсивных функций (обозначение Big O)

Завтра у меня будет курс информатики, и мне нужна помощь в определении сложности этих рекурсивных функций. Я знаю, как решать простые случаи, но я все еще пытаюсь научиться решать эти сложные случаи. Это были лишь некоторые из примеров проблем, ...

ЗаданNov 20, 2012, 5:28 AMотMichael_19
  • 11голосов
  • 3ответа
  • 0просмотров

Сбой стабильности std :: remove и std :: remove_if?

Недавно (из одного комментария) я узнал, чтоstd::remove а такжеstd:remove_if стабильны Я ошибаюсь, считая, что это ужасный выбор дизайна, поскольку он предотвращает определенные оптимизации? Представьте себе удаление первого и пятого элементов ...

ЗаданDec 11, 2012, 9:33 AMотNoSenseEtAl
  • 6голосов
  • 3ответа
  • 0просмотров

Как посчитать разные значения в списке за линейное время?

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

ЗаданDec 13, 2012, 4:20 PMотpolerto
  • 10голосов
  • 3ответа
  • 0просмотров

Использует функцию Аккермана?

На нашем дискретном курсе математики в моем университете учитель показывает своим ученикамФункция Аккермана [http://en.wikipedia.org/wiki/Ackermann_function]и поручить студенту разработать функцию на бумаге. Помимо того, что функция Ackermann ...

ЗаданSep 14, 2009, 8:58 PMотMichaël Larouche
  • 3голосов
  • 4ответа
  • 0просмотров

Не могу понять сложность этого повторения

Я немного обновляюсь по основной теореме и пытаюсь выяснить время работы алгоритма, который решает проблему размераn путем рекурсивного решения 2 подзадач размеромn-1 и объединять решения в постоянное время. Итак, формула: T(N) = 2T(N - 1) + ...

ЗаданJan 20, 2013, 10:05 AMотCratylus
  • 8голос
  • 1ответ
  • 0просмотров

Какова сложность size () для представления порций TreeSet в Java

интересно, какова сложность времениsize() для части просмотра TreeSet. Скажи яm добавление случайных чисел для установки (и мне наплевать на дубликаты): final TreeSet tree = new TreeSet(); final Random r = new Random(); final int N = 1000; for ...

ЗаданFeb 07, 2013, 10:46 AMотBetlista
  • 1голосов
  • 2ответа
  • 0просмотров

Почему сложность пузырьковой сортировки равна O (n ^ 2)?

Как я понимаю, сложность алгоритма заключается в максимальном количестве операций, выполняемых при сортировке. Таким образом, сложность Bubble sort должна быть суммой арифметической прогрессии (от 1 до n-1), а не n ^ 2. Следующая реализация ...

ЗаданFeb 12, 2013, 10:02 PMотOneTwo12
  • 2голосов
  • 3ответа
  • 0просмотров

Оптимизация наихудшего случая Временная сложность до O (1) для python dicts [закрыто]

Я должен хранить 500M двухзначный символ Unicode в памяти (RAM). Структура данных, которую я использую, должна иметь: Worst Case Space Complexity: O(n) Worst Case Time Complexity: O(1) Я думал о выборе dict, который представляет собой ...

ЗаданMar 03, 2013, 9:53 PMотcodersofthedark
  • 4голосов
  • 2ответа
  • 0просмотров

Сложность вставки n чисел в двоичное дерево поиска

У меня есть вопрос, и он говорит:вычислить сложность в сжатые сроки для процесса вставки n чисел в двоичное дерево поиска ", Это не означает, является ли это сбалансированным деревом или нет. Итак, какой ответ можно дать на такой вопрос? Если это ...

ЗаданMar 10, 2013, 11:47 AMотyrazlik
  • 5голосов
  • 3ответа
  • 0просмотров

Cyclomatic Сложность в куске кода с несколькими точками выхода

У меня есть этот метод, который проверяет пароль: /** * Checks if the given password is valid. * * @param password The password to validate. * @return {@code true} if the password is valid, {@code false} otherwise. */ public static boolean ...

ЗаданMar 13, 2013, 4:06 PMотtmh
  • 5голосов
  • 2ответа
  • 0просмотров

Является ли «раскраска дома тремя цветами» NP?

Рассмотрим описанную проблемуВот [http://www.careercup.com/question?id=9941005] (воспроизведено ниже.) Можно ли свести к этому какую-то более известную NP-полную проблему? Эта проблема: Есть ряд домов. Каждый дом можно покрасить в три цвета: ...

ЗаданMar 26, 2013, 5:29 AMотuser977476
  • 76голосов
  • 7ответов
  • 0просмотров

Является ли журнал Big O (logn) базой e?

Для бинарного типа дерева поиска структур данных я вижу, что обозначение Big O обычно обозначается как O (logn). Строчная буква l в журнале это подразумевает логарифмическую базу e (n), как описано натуральным логарифмом? Простите за простой ...

ЗаданOct 14, 2009, 10:28 PMотBuckFilledPlatypus
  • 14голос
  • 1ответ
  • 0просмотров

Неожиданная сложность общих методов (размер) в Java Collections Framework?

Недавно яВы были удивлены тем фактом, что некоторые коллекции Java неt имеет постоянное время работы метода size (). Хотя я узнал, что параллельные реализации коллекций сделали некоторые компромиссы в качестве компромисса для увеличения ...

ЗаданMar 29, 2013, 11:20 AMотmario
  • 27голосов
  • 3ответа
  • 0просмотров

Объяснение Алгоритма для нахождения точек сочленения или срезанных вершин графа

Я искал в сети и не смог найти никакого объяснения алгоритма DFS для нахождения всех вершин артикуляции графа. Там нет даже вики-страницы. Прочитав, я узнал основные факты ...

ЗаданApr 08, 2013, 5:04 AMотAshish Negi
  • 9голос
  • 1ответ
  • 0просмотров

Существуют ли онлайн-алгоритмы для проверки планарности?

я знаю этотестирование на плоскостность [http://en.wikipedia.org/wiki/Planarity_testing]может быть сделано в O (v) (эквивалентно O (e), так как планарные графы имеют O (v) ребер) времени. Интересно, можно ли это сделать онлайн за O (1) ...

ЗаданOct 22, 2009, 2:19 AMотDoug McClean
  • 15голос
  • 1ответ
  • 0просмотров

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

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

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

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

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

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

Сложность и время выполнения

Я попытался осмотреться, чтобы увидеть, можно ли ответить на мой ответ, но я неСпоткнулся, что может помочь мне. При работе со сложностью во время выполнения »s вы учитываете операнды? Насколько я понимаю, имея дело со временем выполнения, ...

ЗаданJun 24, 2013, 10:34 AMотConor F
  • 37голосов
  • 4ответа
  • 0просмотров

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

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

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

временная сложность или скрытая стоимость &lt;Array Name&gt; .length в Java

Я искал проект в Java и нашелfor цикл, который был написан как ниже: for(int i=1; iМой вопрос: стоит ли рассчитыватьa.length (здесь имя массива)? если нет то какa.length рассчитывается внутренне (означает, как JVM обеспечивает доступ O (1) к ...

ЗаданAug 01, 2013, 1:31 PMотTrying
  • 23голосов
  • 4ответа
  • 0просмотров

Линейное время против. Квадратичное время

Часто в некоторых ответах упоминается, что данное решениелинейныйили что другой квадратичная. Как сделать разницу / определить, что к чему? Может ли кто-нибудь объяснить это как можно проще для тех, кто, как я, до сих порне знаешь?

ЗаданAug 02, 2013, 4:15 PMотAnthony Perot
  • 1005голосов
  • 10ответов
  • 0просмотров

Чем отличаются NP, NP-Complete и NP-Hard?

Каковы различия междуNP,NP-Completeа такжеNP-Hard? Я знаю о многих ресурсах по всему Интернету. Я'Я хотел бы прочитать ваши объяснения, и причина в том, что они могут отличаться от того, чтотам, или есть что-то, что яЯ не в курсе.

ЗаданDec 07, 2009, 12:11 AMотDarthVader
  • 48голосов
  • 7ответов
  • 0просмотров

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

Я видел, что в большинстве случаев временная сложность связана с пространственной сложностью и наоборот. Например, в обход массива: for i=1 to length(v) print (v[i]) endforЗдесь легко видеть, что сложность алгоритма в терминах времени равна O ...

ЗаданSep 08, 2013, 2:41 PMотLittle
  • 11голосов
  • 6ответов
  • 0просмотров

Временная сложность удаления узла в одно- и двусвязных списках

Почему временная сложность удаления узла в двусвязных списках (O (1)) быстрее, чем удаление узлов в односвязных списках (O (n))?

ЗаданDec 13, 2009, 5:46 AMотempty heart
  • 16голосов
  • 2ответа
  • 0просмотров

Как рассчитать временную сложность алгоритма возврата?

Как рассчитать сложность времени для этих алгоритмов возврата и имеют ли они одинаковую сложность времени? Если отличается как? Пожалуйста, объясните подробно и спасибо за помощь. 1. Hamiltonian cycle: bool hamCycleUtil(bool graph[V][V], int ...

ЗаданNov 18, 2013, 1:10 PMотda3m0n
Пред12След