Я читал о некоторых алгоритмах геометрической маршрутизации, там написано, что при использовании эвристик в версии основного алгоритма это может повысить производительность, но лишает асимптотической оптимальности. Почему это так? Должны ли мы...

Предположим, у нас есть две функции f(n) = 2 2 n+1 и g(n)=2 2 n . Я хочу сравнить их темпы роста этих двух функций, используя два разных метода. Метод первый: возьмите соотношение Определим t(n) = f(n)/g(n). Затем t(n) = f(n) / g(n) = 2...

Рассмотрим этот фрагмент кода int sum = 0; for( int i = 1; i <= n*n; i = i*2 ){ sum++ ; } Как сделать быстрый правильный анализ, чтобы получить порядок роста времени работы в худшем случае? Как изменение оператора приращения на i =...

У нас есть следующий метод Java: static void comb(int[] a, int i, int max) { if(i < 0) { for(int h = 0; h < a.length; h++) System.out.print((char)(’a’+a[h])); System.out.print("\n"); return; }...

Любой пример алгоритмов, когда мы предпочитаем временную сложность Big O (n ^ 2) O (n logn)? Я где-то видел этот вопрос, но не нашел ответа.

Я не могу определить, как определить скорость роста функций такого типа. void A(int n){ int i=1, s=1; while(s<=n){ i++; s=s+i; cout<<"hi"; } } Дано, что это O (sqrt (n)), но я не могу понять, как это сделать?

К какому классу Big O относится функция (1/2)^n? Чисто с математической точки зрения кажется, что нам придется поместить его в O (1), потому что 1/2 ^ n приближается к 0 для любого достаточно большого n. Однако, когда дело доходит до...

Я пытаюсь понять правильный ответ на следующий вопрос: скриншот вопроса Ответ заключался в том, что все они были верны, потому что lgn можно назвать тета log8n, который включает в себя все три варианта. Это сбивает меня с толку, потому что...

Мне даны две функции: F 1 (n)=2n+20 и F 2 (n)=n+1. Я должен показать, какой из них лучше. Наш лектор решал аналогичную задачу. Учитывая F 1 (n)=n 2 и F 2 (n)=2n+20, он сделал: F 2 (n)/F 1 (n)=(2/n)+(20/n 2 ) и он сказал, что всегда будет...

Рассмотрим следующее дерево рекурсии для быстрой сортировки, которая постоянно делит подзадачи в соотношении 3 к 1 (источник: Khan Academy ). Я понимаю, что подпрограмма разделения в быстрой сортировке перебирает каждую подзадачу и, таким...