Обратно из оценки конверта потребления оперативной памяти для пузырьковой сортировки в C на массиве из 10 целых чисел возможно систематически?

Question

Можно ли точно оценить на бумаге, сколько ОЗУ будет использовано для простого алгоритма (пузырьковая сортировка) в C на тривиальном наборе данных (массив из 10 целых чисел)? Или проблемы реализации компилятора и заполнения байтов сделают это невозможным?

(учитывая платформу, например 32-битный компьютер x86).

Answer 1

Пузырьковая сортировка может работать на месте, поэтому ей не требуется память, кроме сортируемого массива.

Целочисленный массив из 10 занимает 40 байтов, плюс небольшие накладные расходы, зависящие от платформы.
Если вам нужна действительно точная оценка, вам необходимо учитывать размер исполняемого файла, объем памяти, используемой для управления процессами, и многое другое.Но на x86, который обычно имеет много памяти, об этих вещах действительно не о чем беспокоиться.

Если массив больше, то он занимает 4 байта на целое число, а накладные расходы, которые остаются прежними, становятсянезначителен.Между целыми числами нет заполнения, поэтому для больших массивов все, что вам нужно, это 4 байта на целое число.

Answer 2

Это звучит как домашнее задание, поэтому я задам вам несколько вопросов:

1. Алгоритмы сортировки сортируют свои элементы по месту или они работают с копией?
2. Если ониработать с копией, разве размер скопированного списка не будет доминировать в вычислениях?
3. Если они сортируются на месте, сколько памяти требуется за пределами пространства списка?
4. объем дополнительной памяти в (3) зависит от размера списка?