Описание тега big-o
Обозначение Big-O используется для представления асимптотических оценок сверху. Он описывает соответствующую временную или пространственную сложность алгоритмов. Анализ Big-O дает грубую и упрощенную оценку сложности проблемы.
2
ответа
Как рассчитать эту логарифмическую сложность с помощью суммирования?
Мой вопрос Какова сложность Big-O для этого фрагмента кода? Рассмотрим n как степень 4. for(int i = 1; i <= n; i = i*4) for(int k = 1; k <= i; k++) // constant statement Что я знаю до сих пор Я попытался превратить этот код в суммирование, что…
20 окт '17 в 15:43
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
ответа
Какова ценность производительности в приложении, в долларовом выражении?
Это не просто вопрос для меня, но для всех, кто задается вопросом, как важно сделать вещи более глупыми, как панк (быстрее, лучше и сильнее;)). Я не знаю достаточно об этой теме, хотя я стараюсь изо всех сил, чтобы вещи работали лучше всего. Но мне …
11 мар '13 в 03:11
1
ответ
Временная сложность детектора краев Canny
В настоящее время я пишу исследовательскую работу о новом алгоритме стеганографии. Я использовал детектор краев Canny в какой-то момент в моем алгоритме. В статье мне нужно написать временную сложность нового подхода, которая, в свою очередь, зависи…
03 июл '13 в 21:14
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
3
ответа
Расчет временной сложности максимальной суммы подпоследовательности
Привет всем, я пытаюсь вычислить временную сложность максимальной суммы подпоследовательности. На самом деле я знаю ответ, который O(n^3), и это следует из функции (n^3 + 3n^2 + 2n)/6 У меня вопрос, как эта функция получается.
11 ноя '13 в 18:13
0
ответов
Как, если внутри цикла for изменить большой O (сложность времени) функции?
Я пытался найти что-то подобное, но безуспешно, если такой вопрос существует, мои извинения. Вернуться к теме. Я начал копаться в записи Big O и прочее. Однако я столкнулся с проблемой, когда я понятия не имею, как выражение if внутри этой конкретно…
22 сен '18 в 16:51
3
ответа
Создание лучшего ArrayList
Когда вы вставляете в ArrayList в начале или середине списка, который вы всегда будете иметь O(n) производительность, но вставка в конце может поддерживать O(1) потому что вы просто привязываете его к концу списка. У меня есть идея высокого уровня о…
10 ноя '13 в 18:44
1
ответ
Как рассчитать временную сложность рекурсий с запоминанием?
Какова временная сложность кода ниже? Я знаю, что у него есть рекурсивный вызов несколько раз, поэтому, вероятно, он должен быть равен 3^n, но все равно каждый раз он инициализирует массив длины n, который используется последним, и это меня немного …
20 ноя '15 в 21:50
1
ответ
Пространственно-временная сложность "вложенной" рекурсивной функции
В одном из предыдущих вступительных экзаменов в cs возник вопрос: вычислите пространственную и временную сложность функции f1 как функции от n, предположите, что временная сложность malloc (n) равна O(1), а ее пространственная сложность равна На). i…
26 сен '18 в 14:30
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
1
ответ
Big-O PHP массивов
Прочитав ответы на List of Big-O для функций PHP, я немного удивился. В ответе Кендалла Хопкинса говорится, что поиск php - это O(n) для больших массивов и постоянное время (означает O(1)?!) Для маленьких. Он разместил изображение, содержащее график…
16 авг '13 в 09:08
1
ответ
Какая временная сложность потребуется для решения RSA Factoring Challenge?
Хотя проблема закончилась давным-давно, мне немного скучно, поэтому я решил попытаться разложить некоторые цифры. Сначала у меня был алгоритм O (n), но затем я решил исследовать большие обозначения O. Очевидно (я могу ошибаться), алгоритмы O (n) и а…
09 дек '17 в 11:41
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
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
3
ответа
Смущен на повторение и Big O
Я знаю, что T(n) = T(n/2) + θ(1) может быть результатом O(Log N), и моя книга сказала, что это случай бинарного поиска. Но откуда ты это знаешь? Это просто тот факт, что бинарный поиск каждый раз режет проблему пополам, так что это O(Log N)? And T(n…
16 фев '12 в 23:47
2
ответа
Big O - Bubble сорт
Я написал две разные версии алгоритма Bubble Sort- bubbleSort, традиционная версия алгоритма, который вы увидите в учебниках, и sortIntArray, что очень похоже на bubbleSort но рекурсивно Возможно, это мое недоразумение, но последний вызывающий алгор…
24 дек '17 в 20:59
3
ответа
Почему удаление узла из двусвязного списка происходит быстрее, чем удаление узла из односвязного списка?
Мне было любопытно, почему удаление узла из двойного связанного списка происходит быстрее, чем одиночного связанного. Согласно моей лекции, для двойного связанного списка требуется O(1) по сравнению с O(n) для одного связанного списка. Согласно моем…
08 окт '13 в 02:03
0
ответов
Рассчитать алгоритмическую сложность при вызове другой функции
private static int f(int[] a, int low, int high) { int res = 0; for (int i = low; i <= high; i++) res += a[i]; return res; } /** * * @return the size of the largest gap in the array in which the combined values contained in the indexes are divisi…
03 фев '17 в 18:26