Описание тега complexity-theory
Теория сложности вычислений - это раздел теории вычислений в теоретической информатике и математике, который фокусируется на классификации вычислительных задач в соответствии с присущей им сложностью. В программировании особенно часто используется * амортизированный анализ * для времени или пространства.
5
ответов
Как рассчитать время рекурсивного вычисления n-го числа Фибоначчи?
Как узнать, сколько времени требуется для вычисления n-го числа Фибоначчи на текущей машине? Например, на текущей машине 30-й элемент рассчитывается за 67 мс, а 40-й - за 554 мс. Как рассчитать время для 99-го элемента? int fib(int n) { if( n <= …
11 окт '12 в 16:08
1
ответ
Большая сложность двух вложенных циклов
Я пытаюсь найти сложность Big-O следующего алгоритма: int i, j; for (i = 0; i < n; i += 5) { for (j = 1; j < n; j *= 3) { // O(1) code here } } n размер массива, переданного в метод. Борьба с этим из-за i += 5 а также j *= 3, Я знаю, что это, …
01 июн '14 в 16:44
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
2
ответа
Выбор записи из каждого столбца матрицы и взятие их суммы
У меня есть матрица MXN действительных чисел. Как я могу найти все способы выбора одной записи из каждого столбца так, чтобы их сумма была больше некоторого порогового значения? Наивным способом было бы проверить все способы, но есть ли какие-нибудь…
12 июн '13 в 12:21
1
ответ
Как рассчитать временную сложность рекурсий с запоминанием?
Какова временная сложность кода ниже? Я знаю, что у него есть рекурсивный вызов несколько раз, поэтому, вероятно, он должен быть равен 3^n, но все равно каждый раз он инициализирует массив длины n, который используется последним, и это меня немного …
20 ноя '15 в 21:50
3
ответа
Java Big O нотация 3-х вложенных циклов журнала (n)
Что обозначение Big O будет для следующих вложенных циклов? for (int i = n; i > 0; i = i / 2){ for (int j = n; j > 0; j = j / 2){ for (int k = n; k > 0; k = k / 2){ count++; } } } Мои мысли: каждая петля O(log2(n)) так же просто, как умножи…
23 янв '13 в 06:25
0
ответов
Решение ^3 + b^4 = c^3 + d^3 наилучшего времени выполнения
Примечание: этот вопрос отличается от " Напишите все решения для a^3 + b^3 = c^3 + d^3", потому что мне нужна помощь в понимании времени выполнения алгоритма, а не его алгоритма. В "Взломе кодирования", 6-е издание, стр. 69, есть следующий пример: В…
01 июл '17 в 09:56
1
ответ
Введение в алгоритмы Третье издание - Упражнение 2.3 -3 - Индуктивное доказательство nlg(n)
Я читаю книгу "Введение в алгоритмы", третье издание. В упражнении нас просят использовать индуктивное мышление, чтобы доказать T(n) = {2 if n = 2, 2T(n/2) + n if n > 2^k for k > 1} = nlgn Где lg - база журнала 2. Книга предлагает решение: Bas…
07 июл '15 в 04:21
2
ответа
Вычисление O(n) для hasmap против двоичного поиска
Я пытаюсь уточнить, как рассчитать O (n) для следующего случая: Учитывая отсортированный массив, как бы вы нашли два числа, сумма которых равна заданному числу x в O (n)? Решение O (n) будет: Удалить первый элемент массива (e0) Добавьте это к хэш-ка…
20 фев '17 в 12:57
1
ответ
Нахождение сложности данного кода
Я борюсь, чтобы найти сложность данного кода. Я думаю, что я борюсь с определением правильной сложности и как на самом деле анализировать сложность. Код для анализа выглядит следующим образом: public void doThings(int[] arr, int start){ boolean foun…
10 ноя '16 в 15:05
1
ответ
Рекурсивные замыкания (генератор функций)
Я изучал функциональное программирование, и я пришел к мысли, чтобы собрать математические операторы.counting -> addition -> multiplication -> power -> ... Естественно, вышел простой и самый наивный код, чтобы выразить это, и это работае…
21 мар '12 в 22:27
3
ответа
Каковы сложности BigInteger.pow и BigInteger.isProbablePrime?
Каковы сложности методов Java 7 pow а также isProbablePrime в BigInteger учебный класс? Я знаю, что простая реализация теста Рабина имеет сложность O(k(log(n))^3) и может быть уменьшена путем включения алгоритма Шёнхаге-Штрассена для быстрого умноже…
03 окт '11 в 06:41
3
ответа
Алгоритм немонотонной временной сложности
В качестве мыслительного упражнения я пытаюсь представить алгоритм, который имеет немонотонную кривую сложности. Единственное, о чем я мог подумать, это какой-то алгоритм с асимптотическим решением в конечностях. Существует ли такой алгоритм, имеющи…
03 сен '10 в 21:06
2
ответа
Каков порядок роста наихудшего времени выполнения следующего фрагмента кода в зависимости от N?
int sum = 0; for (int i = 1; i <= N; i = i*2) for (int j = 1; j <= N; j = j*2) for (int k = 1; k <= j; k++) sum++; Согласно решению это NlogN. Однако я думал, что это будет просто логин. i цикл for повторяет logN раз, потому что я удваиваюс…
07 сен '14 в 04:34
1
ответ
Вызов функции cProfile.run против сложности
Когда я звоню cProfile.run('myFunction1') возвращается с несколькими вызовами функций. Я хотел бы сравнить различные версии myFunction и найти наиболее эффективную (например, с наименьшей сложностью). Какая связь между function calls и complexity? Ч…
29 июл '13 в 08:26
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
2
ответа
Априорный и асимптотический уровень сложности
Как определить априорную и асимптотическую сложность следующего программного кода? #include<stdio.h> int br_nacina_zaba(int br_lopoca, int tren_poz, int korak) { if (korak == 18) return 0; else if (tren_poz == br_lopoca) return 1; else if (tre…
14 апр '11 в 22:13
1
ответ
Подсчет общего количества циклов
Я пытаюсь вычислить общее количество раз, когда выполняется самый внутренний оператор. count = 0; for i = 1 to n for j = 1 to n - i count = count + 1 Я полагал, что самое большее, что цикл может выполнить - это O(n*ni) = O(n^2). Я хотел доказать это…
20 ноя '12 в 00:57
1
ответ
Как мне добраться до финального выражения в T(n)
Я читал об алгоритмической сложности, и я понимаю, как добраться до формулы ниже: но не похоже, что вы получите эту формулу после очистки суммы: Разве это внутренние члены суммы могут быть нарисованы снаружи, а внутри было бы что-то вроде бесконечно…
28 апр '16 в 19:23
1
ответ
Как рассчитать сложность рекурсивной функции?
Какой самый интуитивно понятный способ вычислить сложность времени и пространства (обозначение Big O) следующей рекурсивной функции? function count(str) { if (str.length <= 1) { return 1; } var firstTwoDigits = parseInt(str.slice(0, 2), 10); if (…
27 май '16 в 09:13