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

  • Автор темы Blade
  • Дата начала
Статус
Закрыто для дальнейших ответов.
B

Blade

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

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

grigsoft

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

Blade

Гость
#3
А как быть если в программе более 10 функций?
Что-то типа этого:
Код:
float func1 (float *dP)
{
float F=0;
for(int n=0;n<16;n++)
F+=dP[n]*dP[n];
f/=16;
return(F);
 

grigsoft

Well-Known Member
15.11.2005
735
0
#5
Если верить ссылке, то
можно определить функцию емкостной сложности ПАМЯТЬ (n), дающую границу для максимального числа одновременно существующих скалярных значений при выполнении $A$ на входных данных размером $n$.
Так что без разницы сколько там функций - вопрос сколько памяти может быть занято по максимуму.

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