Рассчитать время работы алгоритма - PullRequest
Новая
       20

Рассчитать время работы алгоритма

0 голосов
/ 23 марта 2020

Время работы удовлетворяет повторению T (n) ≤ T (n / 2 + 1) + O (1). За исключением +1 и потолка в рекурсивном аргументе, который мы можем игнорировать, это повторение двоичного поиска, решение которого T (n) = O (log n)

Я сбит с толку о том, как T(n) ≤ T(n/2+1)+O(1) рассчитывается как T(n) = O(log n).

1 Ответ

1 голос
/ 23 марта 2020

Я не совсем понимаю, как T(n) ≤ T(n/2+1)+O(1) рассчитывается как T(n) = O(log n).

Это не , вычисляется . Это признано как то же самое. То есть повторение, выраженное как T(n) = T(n/2) + O(1), является «общеизвестным» повторением, соответствующим двоичному поиску. И благодаря другому анализу также «хорошо известно», что сложность бинарного поиска составляет O(log n).

Таким образом, с помощью переходного свойства мы можем сказать, что, поскольку T(n) в этом случае точно то же самое, что бинарный поиск, то также верно и то, что T(n) = O(log n).

См., например, https://users.cs.duke.edu/~ola/ap/recurrence.html

Recurrence Relations to Remember
My suggestion is to do what we do in our classes: show students the "big five" recurrence
relations below and ask them to remember what algorithms these are associated with. We
ask our students to solve other recurrence relations, but we really want them to reason
about recursive functions using the recurrence relations below more than knowing how to
solve any given recurrence relation. We also want students to be able to derive a
recurrence relation from a recursive function --- more on that later.

    T(n) = T(n/2) + O(1)
    T(n) = T(n-1) + O(1)
    T(n) = 2 T(n/2) + O(1)
    T(n) = T(n-1) + O(n)
    T(n) = 2 T(n/2) + O(n)

Before continuing, or with your class, try to fit each of the above recurrence
relations to an algorithm and thus to its big-Oh solution. We'll show what these
are below. Of course for practice you can ask your students to derive the solutions
to the recurrence relations using the plug-and-chug method.

    Recurrence                          Algorithm               Big-Oh Solution
    T(n) = T(n/2) + O(1)      Binary Search                         O(log n)
    T(n) = T(n-1) + O(1)      Sequential Search                     O(n)
    T(n) = 2 T(n/2) + O(1)    tree traversal                        O(n)
    T(n) = T(n-1) + O(n)      Selection Sort (other n2 sorts)       O(n2)
    T(n) = 2 T(n/2) + O(n)    Mergesort (average case Quicksort)    O(n log n)
...