|
Каким образом вычисляется временная сложность: верхняя граница (O) и нижняя граница (o)? Интересует формальное описание, с примерами, применительно к машинам Тьюринга. Например, есть задание из "Sipser: Introduction to the Theory of Computation, Second Edition"
Какие зависимости использовать для доказательства, вычисления? задан 2 Фев '12 1:04 
Dex |
|
Правильно ли я поняла, что O - это символ из матанализа? Причем же тут "алгоритмы"? отвечен 10 Мар '12 21:47 
DocentI Я руководствовался следующим определением с википедии
Из вашего объяснения я ровным счетом понял то, что и так знал. Но как рассчитать в общем случае сложность некоторого абстрактного алгоритма? Ведь поверьте, не к математике применительно меня это интересует, а по отношению к программированию. Расскажете подробнее пожалуйста?
(11 Мар '12 20:54)
Dex
В ваших примерах записаны только чисто математические соотношения, на них мы и ориентировались. Как же давать ответ, не видя конкретного алгоритма? Только так, как сказано в Вики, т.е. подсчитать число элементарных действий (скажем, сложений). Есть, конечно, тонкости. Например, равно ли по сложности умножение одному сложению или нескольким? Как учитывать сравнения (при упорядочениях, например)? Но это вопросы, скорее к программистам, т.е. на другой форум.
(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
|
|
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 
Андрей Юрьевич |
|
В таких случаях надо предположить, что утверждение верно и попытатся опровергнуть или доказать его. Со вторым примером легко: Если утверждение верно, то существуют константы с и $%n_0$%, такие что $%nlogn <= c * n^2 $%, для всех $%n > n0$% поделим на n $%logn <= c * n $% это утверждение верно. Во втором примере надо опровергнуть, что $% n <= c * log^2 n$% , сам я не математик, может это тривиальное доказательсто. отвечен 12 Мар '12 18:24 
IronVbif Обратите внимание, что некоторые ответы помечены как хорошие, а один даже принят. Не стоит повторяться. МожетВы знаете что-то про алгоритмы?
(12 Мар '12 22:34)
DocentI
Я программист =) Ответов действительно много. Но все равно решил привести пример, как такие задачи решаются в книжках по анализу алгоритмов.
(12 Мар '12 22:54)
IronVbif
Спасибо, взято на заметку
(12 Мар '12 23:02)
Dex
|
Вы говорите о сложности алгоритмов, а в примерах никаких алгоритмов нет, только матанализ. Непонятно, о чем вопрос.
Символы O и o означают не "границы", а сравнение двух бесконечно больших (бесконечно малых). "O" означет "ограничено по сравнению с", т.е. для бесконечно больших это примерно означает - "растет не быстрее". А "o" - "бесконечно мало по сравнению с"
Но именно этот матанализ служит базой для расчета сложности алгоритмов. И дело в том, что исследуется это все в теории алгоритмов. Меня интересует, как?
Взяты простейшие примеры, хотелось на них разобраться.
Нет, в матанализе ни о каких алгоритмах и не слыхивали! Ваши примеры показывают только, как сравнить по скорости роста две функции от (натурального) параметра n. Каким алгоритмам они соответствуют? Непонятно! Просто весь ход решения разбивается на шаги (столько-то раз сложить, умножить, сравнить) и подсчитывается количество таких элементарных действий в зависимости от размерности задачи (т.е. числа объектов). Это, скорее, раздел дискретной математики, так как число объектов и действий конечно.
Верно, это я бы и назвал алгоритмом. И собственно теперь мне понятно, что от нас хотел Сипсер, а точнее его последователи - наши преподаватели. Спасибо.