Wataru,
Даже не обращая внимание на стрелки. Понятное дело, что можно все довести до абсурда и константы, но ваше двачевско-плюсовое прошлое оправдаться тут не поможет.
Можно было просто сказать, что да, пример был не совсем верный, написать другой. Спор ни о чем)
Автор вопроса цитирует Кормена, который утверждает, что с помощью предподсчета можно ускорить почти любой алгоритм.
Тут мы с помощью предподсчета делаем из линии логарифм. Ускорение? Да.
Следовательно нет смысла говорить о скорость предподсчета, если конечный алгоритм в итоге будет иметь меньшую асимптотику (в контексте данного вопроса)
Wataru,
Вы сами говорите, что некоторые алгоритмы невозможно сделать быстрее линейного времени выполнения и сами же приводите в пример операции, которые вполне легко ускоряются.
Теперь о предподсчете. Что Вы понимаете под медленнее? Построение дерева линейно, запрос это логарифм. Итого получаем линию.
Заметьте, я даже не ссылаюсь на комментарии выше, где говорится о многопоточке (хотя они тоже правы).
Я лишь говорю о том, что Ваш тезис по отношению конкретно к этим операциям неприменим, чем Вы относительно вводите в заблуждение неопытных формучан (так как Ваш ответ помечен как верный). А потом на собесах будут говорить, что у нас суммирование массива всегда линия
Но, например, алгоритм суммирования всех чисел в массиве или поиска минимума вы так не ускорите.
Ваши слова или я придумал?
Когда у нас стоит задача частого обращения этот предподсчет сразу же нивелируется. И кстати момент, когда требуется использовать, можно также легко предподсчитать с помощью производной. Понятное дело, что его никто не будет юзать для подсчета на пару раз. Но тем не менее стоило подобрать пример получше)
Даже не обращая внимание на стрелки. Понятное дело, что можно все довести до абсурда и константы, но ваше двачевско-плюсовое прошлое оправдаться тут не поможет.
Можно было просто сказать, что да, пример был не совсем верный, написать другой. Спор ни о чем)