КАК ПОСЧИТАТЬ ЁМКОСТНУЮ СЛОЖНОСТЬ?

[Blade]

Подскажите, пожалуйста, что такое емкостная сложность и как её расчитать. Как я понял, это размер памяти, занимаемый программой, но ведь это не просто сумма размеров переменных.
Спасибо!

Если надо, могу программу выложить.

 

[grigsoft]

Не уверен на 100%, но обычно это примерная оценка зависимости занимаемой памяти от размерности задачи. Скажем, тебе надо обработать массив из N элементов. Если дополнительных построений ты не используешь, то это будет O(N). Если для решения задачи тебе надо еще построить матрицу NхN, то будет уже O(N^2).
Вообще гугли на "емкостная сложность" - там вполне вменяемые ссылки, типа http://pco.iis.nsk.su/ICP/Practice/dd8-2/node6.html

 

[Blade]

А как быть если в программе более 10 функций?
Что-то типа этого:

float func1 (float *dP)
{
float F=0;
for(int n=0;n<16;n++)
F+=dP[n]*dP[n];
f/=16;
return(F);

 

[Guest]

Как это правильно оформить?

 

[grigsoft]

Если верить ссылке, то

можно определить функцию емкостной сложности ПАМЯТЬ , дающую границу для максимального числа одновременно существующих скалярных значений при выполнении $A$ на входных данных размером $n$.

Так что без разницы сколько там функций - вопрос сколько памяти может быть занято по максимуму.

Как оформить? а я откуда знаю? Так и напиши: в соответствии с алгоритмом емкостная сложность равно O(N).