Комментарии 36
Мне кажется, что в последнее время на хабре стало черезчур много чисел фибоначи.
Поздравляю, вы открыли для себя динамическое программирование
Не может это быть подсчитано с логарифмической сложностью, т. к. вам потребуется использовать «длинную арифметику», которая не умеет перемножать два числа за О(1). Мне одному кажется, что про подсчет чисел Фибоначчи была уже не одна статья на Хабре (зачем тогда изобретать колесо)?
Ну вот из статьи в статью такие комментарии кочуют, как же ж вы не понимаете, что сложность считается относительно некоторой величины, более того, подавляющее число людей считает сложность относительно числа арифметических операций, а не числа ассемблерных инструкций.
Не знаю, как «подавляющее число людей», а математики сложность считают в элементарных операциях. Есть некоторая стандартная модель вычислимости — машина Тьюринга (которая вообще не знает ничего про числа) и несколько ей полиномиально эквивалентных — например, RAM. Если мы разрешим перемножать любые числа за O(1), то можно сгенерировать данные экспоненциального размера за полиномиальное время. Что совсем нехорошо, ибо непонятно, чему это соответствует на машине Тьюринга.
Мы с вами разные математики, видимо. Есть такое дело, что в разных областях считаются разные величины. Вы, конечно, тоже правы, но даже так получается O(log(N)) (см ниже).
Очень разные. Можно узнать точное определение сложности алгоритма в модели машины Тьюринга, которое Вы предлагаете?
И не получается так log(N). N-е число Фибоначи имеет ассимптотику ((1+sqrt(5))/2)^N, что дает экспоненциальную величину и линейное количество символов.
А вот если считать x1=2, x2=x1*x1, x3=x2*x2, ..., то xN = 2^(2^N), что уже требует экспоненциального числа символов для записи, но линейного числа умножений для вычисления.
И не получается так log(N). N-е число Фибоначи имеет ассимптотику ((1+sqrt(5))/2)^N, что дает экспоненциальную величину и линейное количество символов.
А вот если считать x1=2, x2=x1*x1, x3=x2*x2, ..., то xN = 2^(2^N), что уже требует экспоненциального числа символов для записи, но линейного числа умножений для вычисления.
Вы какую то другую математику видимо имеете в виду, какое еще количество элементарных операций? О_О
Зависит от модели. В МТ — один шаг, в RAM — арифметика с числами ограниченного размера, в CPU — один такт.
В общем случае, у нас есть бесконечное пространство состояний, раскладывающееся в произведение бесконечного числа конечных подпространств. Зафиксируем число N, тогда элементарной операцией можно назвать изменение состояне, затрагивающее не более чем N подпространств.
В общем случае, у нас есть бесконечное пространство состояний, раскладывающееся в произведение бесконечного числа конечных подпространств. Зафиксируем число N, тогда элементарной операцией можно назвать изменение состояне, затрагивающее не более чем N подпространств.
Вот я даже исчерпывающую математику проведу: если нам надо найти N-е число фибоначчи, то сложность будет (возьмем алгоритм перемножения длинных чисел в лоб) O(log(N)*k^2), где k — максимальная «длина» длинного числа, используемого в алгоритме (k конечно), а O(log(N)*k^2) == O(log(N)) по определению O(), а значит таки да, log(N).
k — не конечно, оно зависит от N.
Да, но для любого N существует и конечно max(k(N)) == k, я считаю относительно него, так как это огрубление оценки на O() влияния не произведет.
Для любого N существует и конечно N = k. Тогда O(N) = O(k) = O(1).
Вы говорите чушь, читайте теорию :)
Да я уже понял, что полез в чужой огород со своим уставом, конечно вы правы, уже разобрался.
Не совсем так. Это математика, в ней нет «уставов». В ней есть определения и формальные выводы. И Ваш последний коммент в них ну никак не укладывается.
Именно так. Для меня естественным является вычислитель с атомарной арифметикой действительных (и даже комплексных) чисел. Учитывая, что автор оригинального комментария не сказал, что он говорил о машине тьюринга, так получилось, что я продолжил мыслить в той системе, в которой привык, ну и отсюда и фэйл.
Если бы я не понимал… Зачем, по вашему, оценивают «сложность» некоторого алгоритма? Разве не для того, чтобы потом его сравнить с другим и сказать «асимптотически он будет работать быстрее». А в данном случае, мы не можем принять арифметическую операцию умножения за О(1), т. к. «время», потраченное на ее выполнение, зависит от длины числа (причем, пропорционально квадрату, если использовать «наивный» алгоритм). И, как уже отмечалось в другой статье, как раз использование «длинной арифметики» сильно увеличивает время работы этого алгоритма.
P. S. сложность считают относительно числа арифметических операций, когда все числа «влазят» в машинное слово.
P. S. сложность считают относительно числа арифметических операций, когда все числа «влазят» в машинное слово.
То есть по вашем рассуждениям я так понимаю: если я ввожу int, то сложность алгоритма O(log(N)), а если длинное число, то сложность того же самого алгоритма O(log(N)). Либо же вы считаете этот алгоритм другим алгоритмом, как бы расширенным на длинные числа. В этом случае ваши рассуждения вполне понятны, да.
Во второй раз там «не O(log(N))», опечатался.
Естественно. Если Вы используете для ответа int, то Вы считаете не числа Фибоначчи, а числа Фибоначчи по некоторому модулю (скорее всего, 2^32). И их уже действительно без проблем можно найти за логарифмическое время, а длина ответа вообще ограничена константой.
Это верное замечание. Действительно, факт того, что числа длинные меняет сложность алгоритма. Константы могуть быть разными, но сложность действительно будет линейной, если только в задаче не достаточно нахождения модуля.
сложность считают относительно числа арифметических операций, когда все числа «влазят» в машинное слово.
Если уж до конца занудничать, то при условии, что эти арифметические операции реализованы за константное время, что не для всех машин справедливо. Например в i8080 вообще не было умножения, даже 8-битного
Если уж до конца занудничать, то при условии, что эти арифметические операции реализованы за константное время, что не для всех машин справедливо. Например в i8080 вообще не было умножения, даже 8-битного
Это неважно как раз. Даже если умножение машинных слов реализовать руками, с точки зрения алгоритма это все равно будет константа. Весь сыр-бор начинается именно если размер промежуточного и конечного результата не фиксирован, а пропорционален N.
Это смотря как реализовывать, по-моему. Если суммированием поразрядных сдвигов (или как это правильно называется? 100 лет не занимался), то константа (относительно сложения), а вот если многократным сложением, то линейная зависимость и, скажем, для факториала получаем сложность O(N) относительно умножения, но при этом O(N2) относительно сложения. Или заблуждаюсь?
Я бы ожидал, что используется shift-and-add1, тот, что Вы указали первым. Интересное наблюдение: если при реализации такого алгоритма умножения доступна O(1) проверка «является ли текущий обрабатываемый бит самым крайним слева/справа», то сдвиги-сложения можно остановить в нужный момент, и алгоритм в некотором смысле становится O(ln N).
Еще интересная тема — деление. Вот оно уж точно в той или иной степени итеративное, и количество итераций зависит от входных данных. Другое дело, что современное железо старается эти итерации всячески амортизировать и дать гарантированную оценку сверху сложности операции деления для любых входных данных.
Еще интересная тема — деление. Вот оно уж точно в той или иной степени итеративное, и количество итераций зависит от входных данных. Другое дело, что современное железо старается эти итерации всячески амортизировать и дать гарантированную оценку сверху сложности операции деления для любых входных данных.
Если у нас есть ограничение на размер множителей, т.е. функция умножения определяется на конечном множестве, то ее сложность равна (max_{n <= N,m <= N} time(mul, n, m)) = O(1).
Черт. Во-первых, алгоритм тривиален, во-вторых, недавно была статья на хабре.
Пойду писать статью про поиски в ширину и глубину.
Пойду писать статью про поиски в ширину и глубину.
Мда, действительно была статья. Пойду почитаю. Но там не было про «лесенку», думаю и это будет кому-нибудь интересным.
Да, а давайте еще про все возможные задачи, которые решаются лобовым применением стандартных алгоритмов, статьи писать?
Не скажу за «все возможные» задачи, но про наиболее интересные из них с удовольствием почитал бы.
А почему нет? Для многих начинающих проблемой является перейти от реальной задачи к абстрактному алгоритму.
Ну вот есть реальные задачи, где используются стандартные алгоритмы (из банального — задача о рюкзаке для разбиения категорий по колонкам как можно ровнее). Но вот эти задачи «о лесенках» как раз являются стандартными задачами на тот или иной стандартный алгоритм. И их подборок уже весьма немало в прекрасном изложении. Выбирать из этих задач одну случайную и писать про нее статью — довольно странная идея, как мне кажется.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Раз дощечка, два дощечка — будет лесенка…