Версия для печати темы

Автор: Vitik 22.04.2011 3:52

Всем привет!

Извиняюсь если написал не туда.

На руках работа однокурсника, все знаю что там делается и как, но не могу попасть в заданное число пересылок в сортировке(~количество перемещений данных в память). Не могу сказать что ошибся он, т.к. я не знаю как вычисляется кол-во пересылок
Поэтому помогите пожалуйста, как это подсчитывается.

Буду очень признателен, за ваши ответы.

Автор: Lapp 22.04.2011 4:43

Гм.
Я полагаю, что пересылка - это одна операция с памятью. Например, простой обмен двух переменных a и b между собой с использованием буфера c - это 3 пересылки:

c:= a;
a:= b;
b:= c;

Если так менять два массива в цикле:

for i:=1 to n do begin
  c:= a[i];
  a[i]:= b[i];
  b[i]:= c
end;

- то это уже как бы 3n пересылок..
Но это все не совсем верно на самом деле, так как хороший оптимизирующий компилятор просто разместит переменную c в регистрах, и в результате реальных обменов с памятью останется только два на один такт цикла.

Но вообще-то у этого термина могут быть различные толкования, мне кажется. Если я не прав, пусть меня кто-нить поправит..