Вопросы по теме 'asymptotic-complexity'
Выбрасывать кошек из окон
Представьте, что вы находитесь в высоком здании с кошкой. Кошка может пережить падение из окна низкого этажа, но умрет, если ее сбросят с высокого этажа. Как определить самое длинное падение, которое может выдержать кошка, используя наименьшее...
15027 просмотров
schedule
27.01.2023
Асимптотическая сложность логарифмов и степеней
Итак, ясно, что log(n) равен O(n). Но как насчет (log(n))^2? Как насчет sqrt(n) или log(n) — что ограничивает что?
Существует ряд сравнений, подобных этому: n^a против (log(n))^b.
Я часто сталкиваюсь с этими сравнениями, и я никогда не...
5545 просмотров
schedule
21.08.2022
Дайте асимптотическую верхнюю границу высоты двоичного дерева поиска с n узлами, в котором средняя глубина узла равна Θ(lg n)
В последнее время пытаюсь решить все упражнения в CLRS. но есть некоторые из них, которые я не могу понять. Вот один из них из упражнения 12.4-2 CLRS:
Опишите бинарное дерево поиска на n узлах такое, что средняя глубина узла в дереве равна...
3015 просмотров
schedule
09.10.2022
асимптотическая временная сложность схемных функций
Я пытаюсь научить себя схеме, и концепция, с которой я борюсь больше всего, - это сложность пространства и времени. Я выполнял некоторые упражнения в конце главы и не смог понять следующие два. Я пытаюсь выяснить асимптотическую временную сложность...
348 просмотров
schedule
28.04.2022
Сложность многоступенчатого графа
Я просматривал книгу «Основы компьютерных алгоритмов» для многоэтапной задачи с графом.
В нем говорится:
Algorithm Graph(G,k,n,p)
{
cost[n]=0;
for j=n-1 to 1 step -1 do
{
Let r be a vertex such that<j,r> is an edge of G and c[j,r]+cost[r]...
7642 просмотров
schedule
06.01.2024
Когда полы и потолки имеют значение при решении повторений?
Я сталкивался с местами, где при решении повторений пренебрегали полами и потолками.
Пример из CLRS (глава 4, стр. .83) , где пол не учитывается:
Здесь ( стр.2, упражнение 4.1– 1 ) — это пример, когда потолок игнорируется: (EDIT: я...
7261 просмотров
schedule
24.10.2022
Big Theta, Big O, Big Omega для данной функции
Рассмотрим функцию F: 2^(3*n) + n^2
Может ли функция A: 2 ^ (3 * n) использоваться как большая тета, омега или O как характеристика F? Почему?
Я пересматриваю концепции Big Omega, Big Theta и Big O и наткнулся на этот пример, но не знаю, с чего...
2061 просмотров
schedule
14.08.2023
Асимптотический анализ трех вложенных циклов for
Я хочу рассчитать тета-сложность этого вложенного цикла for:
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
for (int k = 0; k < j; k++) {
// statement
Я бы сказал, что это n ^ 3,...
1442 просмотров
schedule
07.06.2022
Время выполнения следующего цикла
Я пытаюсь найти время выполнения следующего цикла:
int m=1;
for(i=1;i<=k;i++)
{
for(j=1;j<=A[i];j++)
{
B[m]=i;
m++;
}
}
Здесь A — массив, содержащий целые числа, и сумма этих целых чисел равна n. Например,...
159 просмотров
schedule
17.06.2022
Что это значит, когда мы говорим, что временная сложность равна O(M+N)?
Это то же самое, что сказать
O(max(M,N))?
Я изучаю временную сложность, и этот тип сложности появляется снова и снова с графиками. Я не совсем понимаю, что они имеют в виду под
O(M+N),
где M=количество ребер N=количество вершин.
341 просмотров
schedule
01.06.2023
Выполнение инструкции кода C++
Здравствуйте, у меня есть алгоритм на C++, и я хочу найти выполненные инструкции. Код ниже
cin >> n;
for(i=1;i<=n;i++)
for (j = 1; j <= n; j ++)
A[i][j] = 0;
for(i=1;i<=n;i++)
A[i][i] = 1;
теперь, после моих...
174 просмотров
schedule
10.09.2023
Большая тета-привязка 2 рекурсивных вызовов
Учитывая f(x, y) и g(n) :
def f(x, y):
if x < 1 or y < 1:
return 1
return f(x - 1, y - 1) + f(x - 1, y - 1)
def g(n):
return f(n, n)
какова граница Большой Тета для g(n) ?
Я рассудил, что, поскольку x == y,...
432 просмотров
schedule
07.05.2022
Временная сложность подсчета изменений
У меня есть аналогичная проблема со ссылкой: алгоритм смены монет в scala с использованием рекурсии
Код является рекурсивным и выглядит так:
def countChange(money: Int, coins: List[Int]): Int = {
def count(capacity: Int, changes:...
400 просмотров
schedule
05.10.2023
Анализ сложности выполнения функции
Я написал функцию append() на Java, и мне нужно проанализировать ее сложность во время выполнения с помощью O (N) и Θ (N).
Это исходный вопрос:
Предположим, что сложность выполнения append() равна t = O(N) , это означает, что t также...
301 просмотров
schedule
10.03.2023
Bucket Sort — ошибка сегментации
Поэтому я использовал быструю сортировку в своей программе, но теперь хочу уменьшить сложность до O (n). Мне нужно использовать сортировку ведра, чтобы это работало.
Это делает моя программа
Моя программа считывает файл целых чисел и...
1103 просмотров
schedule
20.10.2022
Как выражаются различия в примитивных типах при оценке сложности памяти?
Содержание
Постановка вопроса
Разработка и примеры
Посещенные ресурсы
Ответы (по мере публикации)
Последующие вопросы (как они задуманы)
Вопрос
Как учитывается размер примитивного типа при расчете нотации стиля big-O для...
109 просмотров
schedule
27.12.2022
построение/вставка в отсортированный список
Вот вопрос: у вас есть набор из N случайных чисел, которые нужно вставить в отсортированный список (от меньшего к большему). Каким будет наихудшее асимптотическое время для построения всего списка?
Я знаю, как вставить отсортированный список в...
66 просмотров
schedule
24.06.2023
Какова сложность времени для следующего кода?
Какова временная сложность этого кода?
В этом коде я пытаюсь решить проблему «Разбиение палиндрома». Я использую рекурсию. Я пытаюсь понять ДП. и с помощью этой программы я хочу проанализировать ее временную сложность. Я хочу сравнить его с...
177 просмотров
schedule
24.05.2022
Реализация динамической хеш-таблицы с использованием цепного хеширования
Я пытаюсь реализовать динамическую хэш-таблицу, используя цепное хеширование (каждый элемент массива представляет собой связанный список). Я хочу знать, с точки зрения сложности, какая из следующих возможностей лучше: 1. Я должен удвоить размер...
1048 просмотров
schedule
18.06.2022
Анализ временной сложности с модулем
sum = 0;
for(i=1;i<2*n;i++)
for(j=1;j<i*i;j++)
for(k=1;k<j;k++)
if (j % i == 1)
sum++;
Мне нужно рассчитать временную сложность этого кода в терминах большой нотации O. Я понимаю, как анализировать...
1217 просмотров
schedule
03.03.2023
