Комментарии 14
Большинство людей могут сообразить, как сделать это за константное время. Но под силу ли нам улучшить этот показатель? Даже не сомневайтесь.
Большинство людей найдет в Гугле формулу Бине, которая даст ответ за константное время (или логарифмическое, смотря как считать возведение в степень):
И я не понял, с каких пор логарифмическая сложность считается лучше константной?
Или я что-то фундаментальное не понимаю в этой статье? Может, нужна оговорка, что алгоритм не может оперировать нецелыми числами?
Просто константная перепутана с линейной)
С какого члена ряда Фибоначчи у вас будет потеря точности в младших разрядах?
Примерно с 65 числа Фибоначчи (17 167 680 177 565) погрешность будет около 0.037.
В любом случае это сильно больше, чем может поместится в
P.S. Я не утверждаю, что формула Бине является удобным на практике способом решения данной задачи, просто не упомянуть ее в контексте сложности вычисления чисел Фибоначчи было странно.
В любом случае это сильно больше, чем может поместится в
int, который используется в коде в статье.P.S. Я не утверждаю, что формула Бине является удобным на практике способом решения данной задачи, просто не упомянуть ее в контексте сложности вычисления чисел Фибоначчи было странно.
График
Для формулы Бине использовался numpy.float64, для матричной формулы — numpy.uint64. После 93 члена uint64 переполняется.
Думал глянуть на numpy.float128, но там 128 полезных бит даже документация не гарантирует.
При всём уважении к Алану Чену, на Хабре эту тему уже раскрыли куда лучше.
В прошлый раз эта тема на хабре была раскрыта лучше https://habr.com/ru/post/261159/
Наивное вычисление знаменитой последовательности Фибоначчи производится за экспоненциальное время. Большинство людей могут сообразить, как сделать это за константное время.
Наивное решение — цикл — дает линейное время.
Как посчитать за константное сказать не берусь. Разве что заранее посчитать до нужной точности.
Впрочем, дальше вы пишете Naive: O(n). Так какой вариант имелся в виду? Обычный линейный, рекурсивный или константный (каким бы он ни был)?
Да, переписал вашу реализацию на Си с заменой int на long long, так вот, после 46-го числа наступает переполнение, тогда как обычная циклическая вроде считает нормально. Забавно что ломается только на нечетных
Плюс ко всему вышеперечисленному, у вас ошибка тут:
Поменяются местами не строки, а столбцы.
Если мы поменяем местами две строки единичной матрицы и умножим ее на другую матрицу, это будет эквивалентно перестановке тех же двух строк у другой матрицы
Поменяются местами не строки, а столбцы.
Или я совсем забыл принципы умножения матриц, или после «это будет эквивалентно перестановке тех же двух строк у другой матрицы» результирующая матрица записана неправильно.
Если я правильно понимаю, то перемножаемые матрицы нужно поменять местами, потому что порядок имеет значение.
Если я правильно понимаю, то перемножаемые матрицы нужно поменять местами, потому что порядок имеет значение.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Вычисляем последовательность Фибоначчи за логарифмическое время