Описание тега little-o
В алгоритмическом анализе используются краткие обозначения, чтобы количественно заявить, что одна функция растет строго медленнее, чем другая функция.
1
ответ
Проверка большой тэты, маленькой ох и маленькой омеги с ограничениями?
Скажем, у нас есть две функции f (n) и g(n). Если бы мы хотели проверить, мало ли f (n) oh o (g (n)), было бы правильно сделать следующее: lim n -> infinity f(n)/g(n) and the result would have to = 0 ? Так что, если вышеприведенное выходит до 0, …
12 окт '14 в 00:49
1
ответ
Использование обозначения Little-O
Я думаю, что понять принципиальную разницу между big-O а также little-o нотации. Но кто-нибудь может сказать мне, почему big-O гораздо популярнее на практике?
17 май '13 в 15:48
1
ответ
Когда использовать Big O вместо Theta или Little O
Вопрос об асимптотической записи. Я видел много объяснений асимптотической записи: θ(...) аналогично = O(...) аналогично <= o(...) аналогично < Что может показаться, что если f(n) = O(g(n))то либо f(n) = θ(g(n)) или же f(n) = o(g(n)), Возможно…
13 сен '17 в 23:47
1
ответ
Докажите мало-O из первых принципов
Докажите, что f(n) = 2010n^2 + 1388n принадлежит o (n ^ 3) Little-O Определение Моя работа до сих пор: это должно быть правдой: для ВСЕХ констат c> 0 существует постоянная n0> 0 такая, что 0<=2010n^2 + 1388n<=cn^3 для всех n>n0 Упрощая, мы получаем:…
20 сен '14 в 21:14
1
ответ
Какой f(x) минимизирует порядок g(f(x)), так как x уходит в бесконечность
Предположим, что f (x) стремится к бесконечности, поскольку x стремится к бесконечности и a,b>0. Найдите f (x), который дает самый низкий порядок для как х стремится к бесконечности. Под порядком я подразумеваю обозначения Big O и Little O. Я могу т…
14 июл '17 в 16:57
2
ответа
Алгоритмы - и Little o, и Big Omega с одинаковыми функциями?
У меня есть две функции, f(n),g(n) такой, что f(n)=o(g(n)), чтобы быть ясно, я беру немного о Возможно, с этой информацией, предоставленной мне, что f(n)=Omega(g(n)), Мне кажется, что это невозможно, поскольку определение Литтл-о говорит мне, что fo…
24 мар '17 в 17:04
1
ответ
Может кто-нибудь объяснить, почему f(n) + o(f(n)) = тета (f(n))?
Согласно этой странице: Утверждение: f(n) + o(f(n)) = theta(f(n)) представляется верным. Где: о = мало-о, тета = большая тета Это не имеет смысла для меня. Мы знаем, что o (f (n)) растет асимптотически быстрее, чем f (n). Как же тогда он может быть …
02 окт '13 в 02:02
3
ответа
Экспоненты: Little Oh
Что интуитивно означает nb = o (an) (o - маленький oh)? Я только начинаю самостоятельно учить свои собственные алгоритмы, и мне трудно интерпретировать такие выражения каждый раз, когда я их вижу. Здесь, как я понял, для функции nb скорость роста ра…
06 янв '14 в 05:33
1
ответ
Как решить, является ли 5 ^ нет, Θ или ω из 7^n?
В качестве домашней задачи мне нужно решить, является ли 5n little-o, Θ или little-ω из 7n с математическим обоснованием. Затем мне нужно повторить это после взятия логарифмов обеих сторон. Я изо всех сил пытаюсь понять, что меня просят сделать. Луч…
16 окт '13 в 23:56
1
ответ
О нотации и о нотации
Если f(n) = Θ(g(n)) тогда я знаю f(n) знак равно O(n) а также f(n) = Ω(g(n))， Тогда я бы сказал, что должны существовать c1 и c2 ≥ 0, n1 ≥ 0, для всех n > n1 существует c1*g(n) ≤ f(n) ≤ c2*g(n), доказывать f(n) = c*g(n) + o(g(n)) для некоторого с> 0…
26 янв '17 в 04:45
1
ответ
Сравнение сложностей
У меня есть три вопроса для обзора экзамена: Если f(n) = 2n - 3 дать две разные функции g(n) а также h(n) (так g(n) не равно h(n)) такой что f(n) = O(g(n)) а также f(n) = O(h(n)) Теперь сделайте то же самое снова с функциями g'(n) а также h'(n), но …
15 мар '15 в 14:15
7
ответов
Пример алгоритма, который слишком сложен по времени?
Сколько бы я ни искал в Интернете, я не могу найти примеры алгоритмов, которые на практике не разрешимы из-за количества времени, которое они затрачивают на вычисления. Я пытался придумать пример, такой как подсчет числа, размера и местоположения ка…
16 окт '16 в 04:54
3
ответа
Доказательство, что если g(n) равно o(f(n)), то f(n) + g(n) есть тета (f (n))
Поэтому я борюсь с доказательством (или опровержением) вышеуказанного вопроса. Я чувствую, что это правда, но я не уверен, как это показать. Опять же, вопрос в том, что если g (n) равен o (f (n)), то f(n) + g(n) означает тета (f (n)) Обратите вниман…
18 янв '16 в 21:28
3
ответа
Непонятно, как понимать нотацию
У меня проблемы с этой одной проблемой 9n <= cn^3 в основном я могу приступить к 9/c <= n^2 Но как мне решить остальное?
07 фев '14 в 10:53
3
ответа
Если f(n) = o(g(n)), то есть 2^(f(n)) = o(2^(g(n)))?
Обратите внимание, что я спрашиваю о маленьком о здесь (см. Аналогичный вопрос здесь) - для большого О, это явно неправильно - для маленького - это кажется правильным, но, кажется, не могу доказать это... РЕДАКТИРОВАТЬ: рад, что я поднял дискуссию:)…
30 мар '12 в 08:14
5
ответов
Разница между обозначениями Big-O и Little-O
В чем разница между обозначением Big-O O(n) и Little-O обозначения o(n)?
01 сен '09 в 20:22
2
ответа
Как завершить это в O(1)
Я только что получил это от компании для теста на собеседование, и я с легкостью прошел его, но они сказали, что мои функции были в порядке (n). Вот вопросы Напишите класс IntegerTracker с этими методами: track(int) - Receives an integer for trackin…
05 янв '18 в 15:52
2
ответа
Есть ли у маленьких и маленьких омега верхние / нижние границы?
Я знаю, что Big-O определяет верхнюю границу, а Big-Omega определяет нижнюю границу. Я не смог найти в Google информацию о том, определяют ли Little-o и Little-Omega верхние / нижние границы. Я читал, что у них жесткие границы, но означает ли это, ч…
25 сен '15 в 05:00
1
ответ
Относится ли f(x) = 2*x + 1 к $o(X)$?
Предположим, что функция f: R -> R определена как f(x) = mx + c для некоторых m, c > 0 и x в R. Принадлежит ли f (x) к o(x)? Если ответ "НЕТ", можем ли мы заключить, что o (x) не содержит должным образом набор сублинейных функций? Причина, по которо…
11 дек '16 в 08:41
0
ответов
Как доказать, что f(n)=Θ(g(n)) => f(n)=cg(n)+o(g(n))
Вопрос в том, чтобы доказать, верно ли следующее или нет. f(n) = Θ(g(n)) => f(n) = cg(n) + o(g(n))для некоторой реальной константы c > 0, примечание: о мало о Я пытался сделать следующее:o(g(n)) средства <cg(n)для некоторой константы c след…
25 янв '17 в 03:00