Ранжирование больших функций по сложности - PullRequest
Новая
       12

Ранжирование больших функций по сложности

0 голосов
/ 20 ноября 2018

Я пытаюсь ранжировать эти функции - 2n, n 100 , (n + 1) 2 , n · lg (n), 100n, n !, lg (n) и n 99 + n 98 - так что каждая функция является биг-О следующей функции, но я не знаю метод определения, является ли одна функция большой-О другого.Я был бы очень признателен, если бы кто-нибудь мог объяснить, как я поступил бы так.

Ответы [ 2 ]

0 голосов
/ 21 ноября 2018

Обычно, когда цикл является вложенным, мы умножаем значения на O(outerloop max value * innerloop max value) n и так далее.например, for (i to n){ for(j to k){}} здесь означает, что вы скажете для i = 1 j = 1 к k, т.е. 1 * k, затем i = 2, j = 1 к k, т. е. O(max(i)*max(j)) implies O(n*k)..Кроме того, если вы хотите найти порядок, вам нужно вспомнить основные операции с логарифмическим использованием, такие как O(n+n(addition)) <O(n*n(multiplication)) for log it minimizes the value in it saying O(log n) <O(n) <O(n+n(addition)) <O(n*n(multiplication)) and so on.. Таким образом, вы можете работать и с другими функциями.

Подход должен быть лучше, сначала обобщив уравнениедля расчета сложности времени.как n! =n*(n-1)*(n-2)*..n-(n-1) так что где-то O (nk) будет обобщать сложность форматированного худшего случая, как это можно сравнить, если k = 2, то O(nk) =O(n*n)

0 голосов
/ 20 ноября 2018

Если у вас есть опыт программирования. Скажем, у вас есть код ниже: 

void SomeMethod(int x)
{       
    for(int i = 0; i< x; i++)
    {
            // Do Some Work
    }
}

Обратите внимание, что цикл выполняется для x итераций. Обобщая, мы говорим, что вы получите решение после N итераций (где N будет значением x ex: количество элементов в массиве / входе и т. Д.). Так что этот тип реализации / алгоритм, как говорят, имеет временную сложность порядка N, записанную как O (n)

Аналогично, вложенное значение для (2 цикла) равно O (n-квадрат) => O (n ^ 2)

Если вы приняли бинарные решения и сократили возможности пополам и выбрали только половину решения. Тогда сложность O (log n)

Найдена эта ссылка , чтобы быть интересной.

Для: Химаншу

В то время как Ссылка объясняет, как сложность log (base2) N проявляется очень хорошо, позвольте мне выразить то же самое в моих словах.

Предположим, у вас есть предварительно отсортированный список, например:

1,2,3,4,5,6,7,8,9,10

Теперь вас попросили найти, существует ли 10 в списке. Первое решение, которое приходит на ум - это просмотреть список и найти его. Что означает O (n). Можно ли сделать это лучше?

Подход 1:

Как известно, список уже отсортирован в порядке возрастания Итак:

  • Список прерываний в центре (скажем, в 5).
  • Сравните значение Center (5) со значением поиска (10).
  • Если значение центра == Значение поиска => Найден элемент
  • Если Center Выполните вышеуказанные шаги для правой половины списка
  • Если Центр> Поиск значения => Выполнить вышеуказанные шаги для левой половины списка

В этом простом примере мы найдем 10 после 3 или 4 перерывов (в: 5, затем 8, затем 9) (в зависимости от того, как вы реализуете)

Это означает, что для N = 10 элементов - время поиска было 3 (или 4). Положите сюда немного математики;

2 ^ 3 + 2 = 10 для простоты скажем

2 ^ 3 = 10 (почти равно --- это просто для простой логарифмической базы 2)

Это можно переписать как:

Log-Base-2 10 = 3 (опять почти)

enter image description here

Мы знаем, что 10 - это количество элементов, а 3 - количество разрывов / поисков, которые мы должны были сделать, чтобы найти элемент. Становится

log N = K

Это сложность алгоритма выше. O (log N)

...