N
бпф
Size: a a a
2021 June 22
пп
только там как раз от количества элементов зависит
пп
То есть n
N
а именно o(log n)?
такого не знаю
такого не знаю
V
Давайте тогда считать размер входных данных как длину битового представления числа
Тогда сложность будет О(exp(-n)), если не ошибаюсь
Тогда сложность будет О(exp(-n)), если не ошибаюсь
N
хорошо даже если квантовый компьютер
выполняет с n ячейками 2^n операций
это предел помоему
выполняет с n ячейками 2^n операций
это предел помоему
пп
Ну так у нас всегда ожидается одинаковое количество бит
пп
у нас же фиксированный размер переменной
q
Найдется такое число K, что K * на оценку, которая заключена под big O будет больше при любыхвходных данных, ну это своими словами
пп
Да, это и называется асимптотика
N
логарифм помоему самый быстрый алгоритм быстрее не может быть я думаю
q
Ребят, вы обычно где аудио книги берете? Мб, бота знаете в телеге?!
V
А, да, вы наверное правы
Если сделать не фиксированным, то придется н операций на считывание тратить
Если сделать не фиксированным, то придется н операций на считывание тратить
q
Что это значит? Есть константа, вообще
V
По такому определению да, не может быть меньше н
N
ну я про саму скорось роста функции сложности
пп
ну вообще я не умею в теорию алгоритмов, там вроде как все эти формальности с реализацией опускаются (или нет?). я же все ещё глупенький выпускник .
V
Но вообще на той же Вики есть примеры логарифмических алгоритмов
https://ru.m.wikipedia.org/wiki/%D0%92%D1%80%D0%B5%D0%BC%D0%B5%D0%BD%D0%BD%D0%B0%D1%8F_%D1%81%D0%BB%D0%BE%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D1%8C_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D0%B0
https://ru.m.wikipedia.org/wiki/%D0%92%D1%80%D0%B5%D0%BC%D0%B5%D0%BD%D0%BD%D0%B0%D1%8F_%D1%81%D0%BB%D0%BE%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D1%8C_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D0%B0
q
Ну константа еще есть)
N
думаешь при увеличении числа элементов алгоритм может работать с той же скоростью?