Вопросы по теме 'asymptotic-complexity'
Big O Обозначение выражения
Если у меня есть алгоритм, для выполнения которого требуется 4n^2 + 7n ходов, каков его O? О(4n^2)? О (п ^ 2)?
Я знаю, что 7n обрезается, но я не знаю, должен ли я сохранить коэффициент n^2 или нет.
Спасибо
3046 просмотров
schedule
03.03.2023
Решение повторений
Я пытаюсь решить данную рекурсию, используя дерево рекурсии, T(n) = 3T(n/3) + n/lg n.
На первом уровне (n/3)/(log(n/3)) + (n/3)/(log(n/3)) + (n/3)/(log(n/3)) = n/(log(n/3)) .
На втором уровне оказывается n/(log(n/9)) .
Могу ли я обобщить...
11025 просмотров
schedule
29.08.2022
Функция, которая является Big O (1), но не Ω (1)
Могут ли некоторые помочь мне с функцией, которая является Big O (1), но не Ω (1), и наоборот? Некоторое объяснение очень поможет.
2235 просмотров
schedule
28.08.2022
Вопрос про большой O и большой Omega
Я думаю, что это, вероятно, вопрос новичка о нотации большого O. Скажем, например, у меня есть алгоритм, который рекурсивно разбивает весь список (O(n)), а затем собирает его обратно (O(n)). Я предполагаю, что это означает, что эффективность O (n) +...
404 просмотров
schedule
11.07.2023
Самый быстрый алгоритм для нахождения наибольшего интервала (i,j) такого, что ai + ai+1 ++aj = bi + bi+1 ++bj в массивах a и b
Я столкнулся с этой проблемой при подготовке к экзаменам.
Учитывая два массива чисел a1,..., an и b1,....,bn, где каждое число равно 0 или 1, самый быстрый алгоритм для нахождения наибольшего интервала (i,j), такой что , ai + ai+1 +....+aj = bi +...
1879 просмотров
schedule
11.01.2023
Асимптотическая временная сложность вставки n элементов в двоичную кучу, уже содержащую n элементов
Предположим, у нас есть двоичная куча из n элементов и мы хотим вставить еще n элементов (не обязательно один за другим). Какое общее время потребуется для этого?
Я думаю, что это тета (n logn), так как одна вставка занимает logn.
6469 просмотров
schedule
24.03.2023
Пример немонотонной сложности в наихудшем случае
Кто-нибудь знает о естественной программе или алгоритме, который имеет немонотонное поведение в худшем случае?
Под немонотонным поведением в наихудшем случае я имею в виду, что существует натуральное число n такое, что время выполнения в наихудшем...
120 просмотров
schedule
22.02.2023
Как добавить Big O и Big Omega
Если алгоритм имеет два подалгоритма, то в лучшем случае для подалгоритма A1 для данного входа это худший случай для подалгоритма A2. Как я могу найти общую сложность алгоритма? Просто я имею в виду Ω(N) + O(N)=? Я знаю, что если алгоритмы...
1786 просмотров
schedule
13.01.2024
Временная сложность, бинарное (поисковое) дерево
предположим, что у меня есть полное бинарное дерево до определенной глубины d . Какова будет временная сложность обхода (обхода предварительного заказа) этого дерева.
Я сбит с толку, потому что знаю, что количество узлов в дереве равно 2 ^ d,...
4312 просмотров
schedule
24.02.2023
временная сложность алгоритмов поиска сегмента линии или пересечения ребер
Я сделал краткий обзор литературы по проблемам пересечения и расположения линий в вычислительной геометрии. Большинство из них основано на алгоритме плоской развертки. С точки зрения вычислительной сложности мне кажется, что асимптотические...
532 просмотров
schedule
21.01.2023
Строить рекуррентное отношение для этого кода?
Мне нужно построить рекуррентное соотношение для следующего алгоритма (T(n) обозначает количество элементарных действий) и найти его временную сложность:
Alg (n)
{
if (n < 3) return;
for i=1 to n
{
for j=i to 2i
{...
483 просмотров
schedule
14.04.2022
Как рассчитать верхнюю границу временной сложности («большой O») рекурсивной функции?
Предположим, у меня есть рекурсивная функция T , и я хочу вычислить верхнюю границу сложности таймера этой функции.
T(1) = 3
T(n) = 3T(n/3) + 3.
Как найти верхнюю границу временной сложности T(n)?
1592 просмотров
schedule
05.04.2023
Временная сложность алгоритма Крускала?
Я рассчитываю временную сложность для алгоритма Крускала, подобного этому (пожалуйста, смотрите алгоритм на приложенном изображении)
T(n) = O(1) + O(V) + O(E log E) + O(V log V)
= O(E log E) + O(V log V)
as |E| >= |V| - 1
T(n) = E log E +...
70519 просмотров
schedule
29.05.2023
Стоимость слияния двух хэш-карт
Скажем, у меня есть два HashMaps, как показано ниже.
HashMap<Character, Integer> map1 = new HashMap<Character, Integer>();
HashMap<Character, Integer> map2 = new HashMap<Character, Integer>();
Теперь я хочу объединить...
538 просмотров
schedule
02.10.2022
Временная сложность этой рекурсивной функции генератора k-комбинаций Python
Я искал алгоритм k-комбинации Python и нашел здесь эту маленькую красоту https://stackoverflow.com/a/2837693/553383
Есть идеи о его T(n) и/или временной сложности?
Вот код, который вы найдете по ссылке выше:
def choose_iter(elements,...
956 просмотров
schedule
22.11.2022
Как провести асимптотический анализ этого странного повторения?
Я наткнулся на это странное рекуррентное уравнение:
T(n,h) = T(n/2, h1) + T(n/2, h-h1) + nh
а также:
T(1,h) = O(h)
Мне нужно найти асимптотическую верхнюю границу . Я никогда не сталкивался с рекуррентным отношением с двумя...
137 просмотров
schedule
07.02.2023
Сравнение последовательного поиска с бинарным поиском
Предположим, у меня есть несортированный массив действительных чисел длиной N . Я хочу найти наибольшее неположительное число y , а затем первое число x меньше y в массиве, а первое число z больше y .
Я хотел бы теоретически сравнить...
1623 просмотров
schedule
14.04.2022
Преобразование упорядоченного списка имен в упорядоченный список оценок
Это вопрос интервью.
Предоставьте оптимальное решение для достижения этой цели: Входные данные : список записей учащихся, отсортированный по имени. Выходные данные : список записей учащихся, отсортированный по оценкам, то по названию класс может...
61 просмотров
schedule
06.10.2022
Рост логарифмических, квадратичных и степенных функций с использованием асимптотической записи
Расположите функции в соответствии со скоростью роста, используя асимптотическую нотацию.
Может ли кто-нибудь подтвердить, является ли приведенная ниже последовательность в порядке возрастания истинной или ложной?
n 0,01 , квадратный...
501 просмотров
schedule
30.06.2022
Что такое сублинейные алгоритмы?
Один из моих товарищей задал мне следующий вопрос.
Which of the following expressions is not sublinear?
O(log log n)
O(n)
O(logn)
O(root(n))
Я прошел через https://en.wikipedia.org/wiki/Time_complexity#Sub-linear_time , но не мог, но я не...
18773 просмотров
schedule
02.05.2022
