Структура файловой системы

Begin

Begin

Begin

Begin

Begin

Var

i, j, k: int64;

x, y, z: single;

nMove:= 0;

nCompare:= 0;

for i:= 1 to nCurr -1 do

k:= i;

x:= A[i];

z:= x;

Inc(nMove);

for j:= i + 1 to nCurr do

y:= A[j];

Inc(nMove);

Inc(nCompare);

if y< x then

k:= j; x:= y;

end;

end;

if k <> i then

A[k]:= z; A[i]:= x;

Inc(nMove, 2);

end;

end;

end;

Количество сравнений (nCompare):

i	Min	Max	Average
	n -1	n -1	n -1
	n -2	n -2	n -2
	n -3	n -3	n -3
…	…	…	…
i	n - i	n - i	n - i
…	…	…	…
n -1
∑	n ^2/2- n /2	n ^2/2- n /2	n ^2/2- n /2

Количество переносов (nMove):

i	Min	Max	Average
	n	n +2	n +1
	n -1	n +1	n +2
	n -2	n	n -3
…	…	…	…
i	n - i +1	n - i +3	n - i
…	…	…	…
n -1
∑	n ^2/2+ n /2-1	n ^2/2+ n *3/2+1	n ^2/2+ n /2

Количество переносов с диска (nMoveFromDisk):

i	Min	Max	Average
	n	n	n
	n -1	n -1	n -1
	n -2	n -2	n -2
…	…	…	…
i	n - i +1	n - i +1	n - i +1
…	…	…	…
n -1
∑	n ^2/2+ n /2-1	n ^2/2+ n /2-1	n ^2/2+ n /2-1

Количество переносов на диск (nMoveToDisk):

i	Min	Max	Average
			?
			?
			?
…	…	…	…
i			?
…	…	…	…
n -1			?
∑	0	2 n- 2	?

Количество безусловных переносов в памяти (nMoveInMemoryConst):

i	Min	Max	Average
…	…	…	…
i
…	…	…	…
n -1
∑	n -1	n -1	n -1

Перед оценкой количества «случайных» переносов имеет смысл ввести понятие гармонического числа:

Асимптотическая формула для гармонического числа:

,

– число Эйлера,

. (1)

Результаты применения формулы (1):

	1.83333	2.08333	2.28333	2.45000	2.59286	2.71786
	1.83324	2.08330	2.28332	2.44999	2.59285	2.71786

Количество случайных переносов в памяти:

i	Min	Max	Average
j =2	j =3	j =4	…	j	…	j = n
	n	2 n -1	1/2	1/3	1/4	…	1/ j	…	1/ n
	n -1	2 n -3	—	1/2	1/3	…	1/(j -1)	…	1/(n -1)
	n -2	2 n -5	—	—	1/2	…	1/(j -2)	…	1/(n -2)
…	…	…	…	…	…	…	…	…	…
i	n - i +1	2 n -2 i +1	—	—	—	…	1/(j - i +1)	…	1/(n - i +1)
…	…	…	—	—	—	…	…	…	…
n -1			—	—	—	…	…	…	1/2
∑	n ^2/2+ n /2-1	n ^2-1	=???

.

(2)

Члены вида отброшены.

Для численной проверки сделанных оценок предлагается проект, действующий следующим образом.

Массив A заполняется случайными числами с помощью вспомогательной процедуры FillArray.

Проверка того, является ли массив отсортированным, проводится процедурой IsArraySorted – как до сортировки, так и после.

Процедура ShowArray вызывается, при необходимости, для показа массива.

Сортировку изученными методами проводят следующие процедуры:

InsertSort – сортировка вставками,

BubbleSort – сортировка методом пузырька,

StraightSelectionSort – сортировка методом прямого выбора.

Для каждой процедуры сортировки проводится цикл экспериментов, управляемый параметром цикла k. При каждом следующем k число элементов массива nCurr удваивается по сравнению с предыдущим случаем.

– это наблюденное число переносов при последнем значении nCurr.

– это наблюденное число переносов при предыдущем значении nCurr. (И совсем не обязательно, чтобы именно в два раза меньшим).

Если

,

то

,

откуда

, .

Для рассмотренных сортировок эти формулы позволяют убедиться в верности оценок для среднего числа переносов и сравнений. Для всех случаев, кроме оценки числа «случайных» переносов в памяти в сортировке методом прямого выбора.

В ПЭВМ вся область памяти ВЗУ разбивается над подобласти, называемые логическими дисками. Логическому диску обычно соответствуют: накопители на гибких магнитных дисках, накопители на оптических дисках (CD-Rом), вся память либо ее часть накопителя на жестких магнитных дисках. Логическим дискам присваиваются имена A, B, C и т.д. Размещение файлов на логических дисках подчиняется иерархическому принципу, который реализуется с помощью каталогов. Каталог – это специальный файл, в котором содержатся сведения о других файлах. Любой файл, хранящийся на диске зарегистрирован, по крайней мере, в одном каталоге. При регистрации фиксируется полное имя файла, время и дата создания или изменения файла, размер файла в байтах и т.д. В любом каталоге кроме файлов могут быть зарегистрированы и другие каталоги, которые в этом случае называются подкаталогами, а регистрирующий их файл – родительским каталогом. Каталог, не входящий в другие каталоги, называется главным или корневым. Все каталоги (кроме корневого) имеют имена, назначаемые пользователем. Корневой – обозначается символом "\" (слэш). Структуру логического диска можно представить в виде иерархии.

Fj (j =1,2,3,4) – j-й файл

Ki (i =1,2…6) – i-й каталог

Дисковод, чье имя указано в приглашении для DOS, называется текущим c:\>

текущий текущий каталог

дисковод (корневой)

C

Каталог, чье имя указано в приглашении последним, называется текущим c:\k1>

текущий текущий

дисковод С каталог К1

При запуске операции доступа к конкретному файлу возможны 2 случая:

1) если имя файла зарегистрировано в текущем каталоге, то для доступа достаточно указать имя файла (см. рис.) С:\К1>F1

2) если имя файла зарегистрировано в другом (не текущем) каталоге, то для доступа перед именем файла необходимо указать путь, то есть цепочку соподчиненных каталогов, через которые необходимо пройти для достижения каталога, содержащего интересующий нас файл (см. рис.). При записи проходимые каталоги разделяются символом "\".

C:\K1>K4 \F3

Дата добавления: 2014-01-06