Я изучаю эту книгу под названием «Введение в анализ алгоритмов» (Роберт Седжвик и Филипп Флажоле), а в первой главе, когда они пытаются проанализировать алгоритм быстрой сортировки, они говорят что-то, что я просто не смог понять вообще. Пытаясь вычислить «требования к ресурсам» для al oop, а именно что-то вроде:
while( a[++i] < v );
, они сказали, что это может быть записано в ассемблере как:
LOOP INC I,1
CMP V,A(I)
BL LOOP
до сих пор Хорошо, я думаю, но затем они упомянули (что для первой оценки) разумно подумать об одной итерации l oop, потребляющей «четыре единицы времени», «по одному на каждую ссылку памяти», говорят они. Я понятия не имею, что они имеют в виду под «единицами времени», и откуда взялся количественный критерий «четыре» и какое отношение имеет ко всему ассемблерный код. быть объяснением аргумента - также кое-что, что я затрудняюсь понять. Просто чтобы прояснить, я не хочу, чтобы кто-то объяснил мне Быструю сортировку, я хочу знать, что эти абстракции в анализе, которые были сделаны, означают независимо. Может ли кто-нибудь помочь мне здесь?