Big-O временная сложность - PullRequest
Новая
       16

Big-O временная сложность

2 голосов
/ 25 октября 2010

Я занимался самообучением в Big-O. Я понимаю, как привести примеры следующих обозначений алгоритмов:

O (N): 

for(int i = 0; i < n; i++)
    sum++;

O (N ^ 2): 

for(int i = 0; i < n; i++)
    for( int j = 0; j < n; j++)
        sum++;

O (N ^ 3): 

for(int i = 0; i < n; i++)
    for( int j = 0; j < n * n; j++)
        sum++;

Я сталкивался с этими обозначениями, которые не совсем понимаю. Как я могу привести примеры этого в терминах алгоритмов?

Может быть, мне следует сформулировать это так: напишите алгоритм, который занимает время выполнения пропорционально:

  1. О ((п ^ 3) / 4)
  2. log n ^ 3
  3. O ((войти ^ 2) п) + О (п)
  4. 4 ^ п
  5. п ^ 3/2

Ответы [ 2 ]

9 голосов
/ 25 октября 2010

Боюсь, вы неправильно понимаете нотацию "Big-O".

Нотация не "выражается" как алгоритм.Скорее, запись Big-O описывает свойство алгоритма.

Таким образом, это не "O (N) может быть выражено как XXX", а скорее "алгоритм XXX имеет сложность O(N) ".

Тем не менее, вполне разумно попросить примеры алгоритмов с определенной сложностью;Вы уже перечислили некоторые.Чтобы ответить на ваши вопросы:

O (4 ^ n) совпадает с O (e ^ n), часто пишется как O (exp (n)) (попытайтесь понять, почему это то же самое). O (4 ^ n) относится к классу алгоритмов с "экспоненциальной сложностью" ( EXPTIME ).Многие важные задачи в математике / CS имеют экспоненциальную сложность (или почти экспоненциальную сложность).

Алгоритм с экспоненциальной сложностью может быть, например, наивным решением задачи дискретного логарифма .

Что касается других сложностей, я не могу привести пример, но вы, вероятно, найдете его, немного погуглив.

0 голосов
/ 25 октября 2010

Алгоритмы, которые вы дали, строго говоря, не Big-O, а Theta. Big-O - это асимптотическая верхняя граница, означающая, что на некоторых худших входных данных будет дано время выполнения, но не для всех входов, где, поскольку Тета является жесткой границей, это означает, что время выполнения всегда будет таким. Рассмотрим, например, алгоритм сортировки, которому в качестве входных данных дан уже отсортированный список, или алгоритм поиска, в котором искомые объекты являются первым элементом в списке (как в этом случае двоичный поиск сравнивается с линейным поиском).

...