Описание тега asymptotic-complexity

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

Функция масштабирования большой o (n+1)^5 / 4n^2

Я расширил (n+1)^5: (n^5+5n^4+10n^3+10n^2+5n+1)/4n^2 упростили и приказали им быть: n ^ 3/4 + 5n ^ 2/4 + 1 / 4n ^ 2 + 10n / 4 + 5 / 4n + 10/4 Я обнаружил, что если я подключу 6 для тестирования, то сначала он удовлетворяет двум: п ^ 5 / 4n ^ 2 = 216…
17 сен '17 в 01:31
1 ответ

Как выглядит Big-O Depth-First-Search = O(V+E)?

Я пытаюсь понять, как / почему сложность DFS составляет O(V+E). Вот моя попытка проанализировать сложность псевдокодового итеративного DFS. DFS(G, t) { 1 stack S = new empty Stack of size G.|V| ... O(1) 2 S.push(t) ... O(1) 3 while(S is not Empty) .…
12 ноя '15 в 05:18
1 ответ

Каковы асимптотические времена выполнения для методов OWL EntitySearcher (например, EntitySearcher.getAnnotations(c, o, factory.getRDFSLabel()))

Я пишу приложение, которое использует как онтологию /owlapi, так и базу данных sqlite, в которой значение определенных полей является IRI из онтологии. Мне интересно, будет ли (асимптотически) быстрее извлекать аннотации rdfs:Label и rdfs:Comment из…
01 сен '18 в 07:53
1 ответ

Big O Рекурсивный метод

У меня есть метод под названием бинарная сумма Algorithm BinarySum(A, i, n): Input: An array A and integers i and n Output: The sum of the n integers in A starting at index i if n = 1 then return A[i] return BinarySum(A, i, n/ 2) + BinarySum(A, i + …
03 мар '18 в 20:18
1 ответ

Означает ли g(n) ∈ O(f(n)) f(n) ∈ Ω(g(n))?

Я просто пытаюсь понять, как работают Big O и Big Omega. Я знаю, что Big O означает не лучше чем, а Big Omega означает не хуже времени бега. Итак, если у меня есть функция g(n) такая, что g(n) = O(f(n)), то могу ли я сказать, что f(n) = Ω (g(n))?
28 апр '16 в 00:26
1 ответ

Нахождение средней сложности случая с вероятностью

Допустим, у нас есть строка n, которая может быть заполнена буквами "a" или "b", например: n = "aaabbbab", "ababababab" и так далее. и мы определяем функцию под названием HalfA(n): count a = 0; for each i in n: if n == 'a' i++; if i >= n.length/2…
21 окт '13 в 14:20
1 ответ

Длинная подстрока без повторяющихся символов

Мне задали этот вопрос в недавнем интервью. Мне нужно найти самый длинный substring без повторяющихся символов. Дано " abcabcbb ", ответ " abc ", длина которого составляет 3. Дано " bbbbb ", ответ " b ", длиной 1. Дано " pwwkew ", ответ " wke ", дли…
09 июн '16 в 09:18
3 ответа

Какова сложность запуска цикла дважды из одного и того же входного массива?

Я новичок в алгоритмах, и очень заинтересован в изучении и реализации их.Изучая их через все доступные онлайн-материалы, которые я могу найти. Я немного запутался по этому поводу - Рассмотрим этот код - for (int i=0; i<n; i++) { ..... } for (int …
11 июн '16 в 16:01
1 ответ

Оценка сложности рекурсивной функции

void f(int n) { if (!n) return; for (int i=0; i<8; i++) f(n/12); g(n,3); } void g(int n, int i) { if (!i) return; for (int j=n; j>0; --j) { g(n,i-1); } } Я пытаюсь оценить сложность этой функции. Вот как я это делаю: Оцените данную сложность. …
20 июн '17 в 19:10
2 ответа

Асимптотическая сложность питона

У меня есть задача найти асимптотическую сложность этого кода Python. for i in range(x): if i == 0: for j in range(x): for k in range(500): print("A ") По тому, что я знаю, это должно быть 500* х. Поскольку первый цикл идет только один раз (i==0), в…
07 ноя '16 в 19:28
4 ответа

Биг-О нотация, найти самый маленький

Дайте наименьшую оценку O(), которую вы можете выполнить для следующих функций: 4n2 + 5n – 8 = O(...) log(n)2 + n = O(...) Если вы, ребята, можете, объясните ответ, а не дайте его мне. Такой вопрос будет на моем среднесрочном плане, и я хочу это пон…
13 июн '11 в 13:47
3 ответа

Расчет сложности?

Я пытался вычислить сложность следующей функции: k=n; while(k>0) g(n); k=k/2; {Comment: this is integer division, so 1/2=0} end while; for(j=0;j<m;j++) f(m); В частности, сложность цикла while. Мне говорят, что сложность g(n) равна O(n), но я …
16 янв '13 в 22:21
1 ответ

Асимптотическая оценка для целочисленного деления

k = n; //integer division while(k > 1) { std::cout << k; k=k/2; } Мне нужно выяснить асимптотическую оценку как функцию от n.
01 май '13 в 16:07
2 ответа

Какова временная сложность этого решения O(N) или O(LogN)?

https://codility.com/programmers/lessons/1-iterations/ Учитывая это: if (largestHole > (bin.length - i) && subHole < (bin.length - i)) { break; } Если длина самого большого отверстия до сих пор меньше, чем длина оставшихся цифр, чтобы…
10 май '17 в 11:52
1 ответ

В чем разница между O(N) + O(M) и O(N + M). Есть ли?

Я решаю проблемы для практики собеседования, и я не могу найти ответ на сложность времени и пространства для следующей проблемы: Имея два отсортированных связанных списка, объедините их в третий список в отсортированном порядке. Давайте предположим,…
16 авг '14 в 06:47
2 ответа

f(n)/log(n) = O(g(n)) ⇒ g(n) = Θ(f(n))?

Можно ли показать, что f(n)/log(n) = O(g(n)) => g(n) = Θ(f(n))? Прямо сейчас я стою здесь: f(n)/log(n) = O(g(n)) ⇒ f(n)/log(n) ≤ c₁⋅g(n) ⇒ f(n)/(c₁⋅log(n)) ≤ g(n) g(n) = Θ(f(n)) ⇒ c₂⋅f(n) ≤ g(n) ≤ c₃⋅f(n) Тогда я говорю: c₂ = 1/(c₁⋅log(n)) ⇒ c₂⋅f…
13 мар '15 в 15:47
3 ответа

Большой O алгоритма, который опирается на сходимость

Мне интересно, можно ли выразить временную сложность алгоритма, основанного на сходимости, с помощью записи Big O. В большинстве алгоритмических анализов, которые я видел, мы оцениваем скорость роста нашей функции на основе размера ввода. В случае а…
19 мар '18 в 20:43
1 ответ

Как бы вы, где один алгоритм предпочтительнее, чем другой алгоритм

Я пытаюсь сравнить два алгоритма и их эффективность. Я пытаюсь найти значение для n, где один алгоритм становится более эффективным, чем другой алгоритм. Любые полезные примеры или ресурсы будут огромной помощью.
25 ноя '17 в 16:35
0 ответов

Обозначение Big O на некоторых примерах

Профессор дал нам несколько примеров, которые можно попробовать дома, но никогда не давал нам ответов, и теперь, когда я готовлюсь к экзаменам, мне бы очень хотелось подробнее остановиться на этом. У нас есть 3 "алгоритма", и мы должны выработать бо…
19 апр '15 в 11:41
2 ответа

Порядок роста для заданных функций

Я попытался отсортировать эти функции в порядке асимптотического роста и хотел бы знать, на правильном ли я пути. 5000log2 (п) sqrt (n) +7 8л п /log2(п) 4nlog2 (п) п ^ 1/100 1/4 n ^ 2 - 10000n.
28 фев '16 в 17:32