Каким образом вычисляется временная сложность: верхняя граница (O) и нижняя граница (o)?

Интересует формальное описание, с примерами, применительно к машинам Тьюринга.

Например, есть задание из "Sipser: Introduction to the Theory of Computation, Second Edition"

  1. $$n^2 = O(nlog^2n)$$ -> не верно
  2. $$nlogn = O(n^2)$$ -> верно

Какие зависимости использовать для доказательства, вычисления?

задан 2 Фев '12 1:04

перемечен 10 Мар '12 21:48

DocentI's gravatar image


9.8k938

Вы говорите о сложности алгоритмов, а в примерах никаких алгоритмов нет, только матанализ. Непонятно, о чем вопрос.

(10 Мар '12 21:33) DocentI

Символы O и o означают не "границы", а сравнение двух бесконечно больших (бесконечно малых). "O" означет "ограничено по сравнению с", т.е. для бесконечно больших это примерно означает - "растет не быстрее". А "o" - "бесконечно мало по сравнению с"

(11 Мар '12 19:37) DocentI

Но именно этот матанализ служит базой для расчета сложности алгоритмов. И дело в том, что исследуется это все в теории алгоритмов. Меня интересует, как?

Взяты простейшие примеры, хотелось на них разобраться.

(11 Мар '12 21:11) Dex

Нет, в матанализе ни о каких алгоритмах и не слыхивали! Ваши примеры показывают только, как сравнить по скорости роста две функции от (натурального) параметра n. Каким алгоритмам они соответствуют? Непонятно! Просто весь ход решения разбивается на шаги (столько-то раз сложить, умножить, сравнить) и подсчитывается количество таких элементарных действий в зависимости от размерности задачи (т.е. числа объектов). Это, скорее, раздел дискретной математики, так как число объектов и действий конечно.

(11 Мар '12 21:15) DocentI

Просто весь ход решения разбивается на шаги

Верно, это я бы и назвал алгоритмом. И собственно теперь мне понятно, что от нас хотел Сипсер, а точнее его последователи - наши преподаватели. Спасибо.

(11 Мар '12 21:16) Dex
10|600 символов нужно символов осталось
2

Правильно ли я поняла, что O - это символ из матанализа? Причем же тут "алгоритмы"?
Если так, то данные соотношения можно опровергнуть/доказать с помощью пределов. Например, второе соотношение означает, что отношение $%\frac{n\log n}{n^2}=\frac{\log n}{n}$% ограничено при стремлении n к бесконечности. Но предел этого отношения (вычисляется по правилу Лопиталя) равен 0, а всякая сходящаяся последовательность ограничена. Итак, $%n\log n$% есть не только "О-большое", но и "о-малое" от $%n^2$%. Аналогично проверяется и первый пример: соотв. отношение стремится к бесконечности и, значит, неограничено.
Для более сложных функций ограниченность не всегда связана с пределом, но в теории сложности алгоритмов, кажется, такие функции не используются.

ссылка

отвечен 10 Мар '12 21:47

изменен 10 Мар '12 21:49

Я руководствовался следующим определением с википедии

В информатике и теории алгоритмов вычислительная сложность алгоритма — это функция, определяющая зависимость объёма работы, выполняемой некоторым алгоритмом, от размера входных данных

Из вашего объяснения я ровным счетом понял то, что и так знал. Но как рассчитать в общем случае сложность некоторого абстрактного алгоритма? Ведь поверьте, не к математике применительно меня это интересует, а по отношению к программированию. Расскажете подробнее пожалуйста?

(11 Мар '12 20:54) Dex

В ваших примерах записаны только чисто математические соотношения, на них мы и ориентировались. Как же давать ответ, не видя конкретного алгоритма? Только так, как сказано в Вики, т.е. подсчитать число элементарных действий (скажем, сложений). Есть, конечно, тонкости. Например, равно ли по сложности умножение одному сложению или нескольким? Как учитывать сравнения (при упорядочениях, например)? Но это вопросы, скорее к программистам, т.е. на другой форум.
Простейший пример: если алгоритм требует полного перебора перестановок (для n исходных объектов), то его сложность равна n!.

(11 Мар '12 21:01) DocentI

А там Вы тоже поставили вопрос так абстрактно? Приведенные примеры программистам, конечно, не нужны. Другое дело: "задача коммивояжера является NP-сложной" - т.е. неполиномиально сложной, количество действий не описывается никаким полиномом. Тут хоть есть о чем говорить.

(11 Мар '12 21:18) DocentI

Вот вы можете объяснить словами, как понять, что nlogn = O(n^2)? Т.е. не на уровне интуитивном, а конкретном, разбиваем на такие-то операции, считаем так то, проверочка тут.

(11 Мар '12 21:25) Dex

На самом деле мое невежество в данном вопросе сводилось к моей же глупости. Я выполнял вычисление сложности nlogn, принимая умножение за базовую операцию, совершенно забыв о сложении. Спасибо.

(11 Мар '12 21:33) Dex

на самом деле есть "абстрактная" теория сложности, которая оперирует детерминированной и недетерминированной машинами Тьюринга и прочей заумью. Но для практических целей это не обязательно. Вы нашли ошибку? Больше не надо отвечать? И при чем тут опять O? Это чисто математическое понятие, если "Шаги" уже подсчитаны.

(11 Мар '12 21:51) DocentI

Вот собственно в отношении нДМТ мне и нужно все это. Я ведь не зря указал книгу Сипсера. И именно из-за того, что в ней оперируют "о" и "О" для обозначения, я их тоже использую. Так, как задачи записаны там, так я их и выложил сюда. И, собственно, с точки зрения Сипсера меня и интересовало как они решаются, математика тут более второстепенная. Отвечать не нужно, спасибо, я разобрался.

(12 Мар '12 1:59) Dex

Боюсь, что здесь нужны узкие специалисты. Пока я вижу хорошие ответы только по классической, непрерывной математике

(12 Мар '12 9:54) DocentI
показано 5 из 8 показать еще 3
10|600 символов нужно символов осталось
2

1) Сложность задачи (обозначим ее N) определяется количеством элементарных операций, необходимых для ее решения, и может быть функцией от каких-то параметров модели. Например, пусть задача состоит в табулировании функции n переменных так, чтобы каждая переменная пробегала m значений. Будем считать элементарной операцией одно вычисление функции, тогда сложность алгоритма N=m^n. Если зафиксировать n и рассматривать функцию N(m), то сложность степенная, если, наоборот, зафиксировать m и рассматривать N(n), то сложность экспоненциальная.

2) Пусть, n-некоторый параметр модели и рассматривается функция N(n). Для того, чтобы ее оценить, существуют базовые элементарные функции ln(n), n^k, exp(n), с которыми реальная функция N(n) сравнивается при помощи символов матанализа O и o. Например, запись N=O(n^2) означает, что с увеличением параметра n сложность растет не быстрее, чем n^2. Если N=o(n^3), - значит N растет медленнее, чем n^3, при увеличении n.

ссылка

отвечен 12 Мар '12 1:51

10|600 символов нужно символов осталось
1

В таких случаях надо предположить, что утверждение верно и попытатся опровергнуть или доказать его.

Со вторым примером легко: Если утверждение верно, то существуют константы с и $%n_0$%, такие что

$%nlogn <= c * n^2 $%, для всех $%n > n0$%

поделим на n

$%logn <= c * n $%

это утверждение верно.

Во втором примере надо опровергнуть, что $% n <= c * log^2 n$% , сам я не математик, может это тривиальное доказательсто.

ссылка

отвечен 12 Мар '12 18:24

Обратите внимание, что некоторые ответы помечены как хорошие, а один даже принят. Не стоит повторяться. МожетВы знаете что-то про алгоритмы?

(12 Мар '12 22:34) DocentI

Я программист =) Ответов действительно много. Но все равно решил привести пример, как такие задачи решаются в книжках по анализу алгоритмов.

(12 Мар '12 22:54) IronVbif

Спасибо, взято на заметку

(12 Мар '12 23:02) Dex
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×34
×3

задан
2 Фев '12 1:04

показан
2259 раз

обновлен
12 Мар '12 23:02

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru