Здравствуйте.
Не могу придумать 2 алгоритма для которых RAM-модель и реализация на языке программирования Си давала существенно различные результаты. Подскажите пожалуйста.
Скиена говорит что такое возможно, но к сожалению не приводит конкретных примеров. Книга (Steven S. Skiena, The Algorithm Design Manual) мне нравится, однако обратите внимание как он обосновывает этот пример. Анатолий, он окончил Иллинойсский университет, но обоснование крайне слабое, в том смысле что позорное, для алгориста (это к нашей недавней дискуссии, но не для того что спорить, а просто наблюдение).

Неравенство Коши и не нужно what if x>y и what if x<=y.

Да ещё и оценку задрал, вместо 3, как видно, спокойно можно писать 2.

White OwlSashaMercury,

ха???

Неконкретный вопрос о неконкретных алгоритмах.
Потом картинка иллюстрирующая работу с О.... Потом спор с этой картинкой...
Саша, ты когда спал последний раз?


Random Access Machine - абстрактная машина, на которой проектируется сложность алгоритмов. Любая простая операция +,-,*,=,call? if - требуется ровно один временное шаг. Каждое обращение к памяти занимает ровно один шаг. Время исполнения алгоритма вычисляется по общему числу шагов в RAM-модели. Эта модель позволяется проектировать сложность алгоритмов. Однако, как правило, умножение занимает больше времени чем сумма в реальных машинах, циклы также могут быть оптимизированы компилятором fe, да и время обращения памяти не всегда постоянно. Несмотря на это чаще всего, RAM-модель хорошо подходит для оценки сложности алгоритмов (и вы все еёё безусловно использовали/используете, только видимо по другому называете). Скиена говорит, что бывают случаи когда происходит значительное несоотвествие RAM-модели с реализацией, но конкретных примеров не приводит.

Хотелось бы увидеть два алгоритма, Сложность RAM первого, fe, O(n^2), а второго O(n^3), а при реализации на Си, при достатчно больших n, интересно было бы наблюдать обратную картину.

Картинка имеет отношение к вопросу, ибо она связана с RAM-моделью.

Anatoly MoskovskySashaMercuryНеравенство Коши
С какого перепугу кто-то должен помнить всю эту математическую пургу, если она выводится в 2 действия в уме на основе программы младших классов?

Это не пурга, он вывел коряво и оценка слабая. Вывод должен быть в одно действие.И он выпускник Иллинойса в конце концов

Про деления там вроде-бы ничего не сказано. Хочется видеть конкретный жизненный пример, а не искусственное усложнение реализации алгоритма. Увидеть что компилятор что-то оптимизировал так, что RAM это никак не могла учесть. Или наоборот. К языку Си данный вопрос имеет прямое отношение, ибо примеры на других языка программирования мне не интересны.

А к этому разделу этот вопрос не имеет никакого отношения. Нужно хорошо знать Си, чтобы привести такой пример. Знать какие места будут хорошо оптимизированы независимо от сложности алгоритма

Anatoly Moskovsky,
a C++ ?

Anatoly Moskovsky,

Я знаю кто компилятор оптимизирует некоторые циклы. Это верно ? Т.е. возможна такая ситуация что цикл из 10^6 итераций выполняться вовсе не будет.

А можете привести пример более серьезной оптимизации ?
Ну например, сумма от 1 до n с шагом d, будет заменена на сумму арифметической прогрессии ? (думаю да) Может быть что-нибудь ещё есть кроме таких примеров?

Здравствуйте.
В данном случае не представляет сложности получить значение r аналитически , но будет ли цикл оптимизирован компилятором или средой разработки ? Не обязательно Си, С++. Любого другого языка.