CD
В двух редакциях
Size: a a a
2020 April 29
CD
а вы видели аналитическую комбинаторику?
Чтобы потом узнать, что это вообще-то не очень важно, потому что вы не можете нормально оценить доступы к памяти
i
Вы все еще не ответили на мой вопрос. Как вы думаете, сколько времени у вас займет точное вычисление числа операций для Фурье в условной двумерной схеме split-radix? В часах
Точное асимптотически считается через вычеты
mq
Кстати, вот пусть зафиксированы числа s и n. Определим A(T, s) как число компонент центроида размера больше s, возникающих в процессе центроидной декомпозиции дерева T.
Определим P(n, s) как максимум A(T, s) по всем деревьям с n вершинами.
Определим P(n, s) как максимум A(T, s) по всем деревьям с n вершинами.
i
и теорию ТФКП достаточно быстро
i
в широком классе задач
CD
Точное асимптотически считается через вычеты
Какое асимптотически? Точное. До единиц
mq
Кстати, вот пусть зафиксированы числа s и n. Определим A(T, s) как число компонент центроида размера больше s, возникающих в процессе центроидной декомпозиции дерева T.
Определим P(n, s) как максимум A(T, s) по всем деревьям с n вершинами.
Определим P(n, s) как максимум A(T, s) по всем деревьям с n вершинами.
Задача: придумать точную оценку для P(n, s).
i
Посмотри в Седжвике анализ алгоритмов
CD
Посмотри в Седжвике анализ алгоритмов
Там этого нет
CD
Ни в одной стандартной книге про FFT деталей вообще нет
i
Там написано в чем разница и преимущество его подхода перед подходом кормена
CD
Там написано в чем разница и преимущество его подхода перед подходом кормена
Подход Кормена обладает одним свойством - точнее этого на практике вы не дадите оценок
CD
И считать ничего не надо
mq
Задача: придумать точную оценку для P(n, s).
((я не могу доказать асимптотику одного алгоса помогите плз))
mq
ну не точную мб просто хорошую
mq
я думаю что там O(n/s+1)
i
Подход Кормена обладает одним свойством - точнее этого на практике вы не дадите оценок
не совсем ястно утверждение
CD
не совсем ястно утверждение
Какая мне разница, какие константы за асимптотиками
2020 April 30
mq
я думаю что там O(n/s+1)
но это прям совсем догадка