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

Тема в разделе "Общие вопросы по С и С++", создана пользователем Blade, 18 мар 2006.

Статус темы:
Закрыта.
  1. Blade

    Blade Гость

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

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

    grigsoft Well-Known Member

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

    Blade Гость

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

    Guest Гость

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

    grigsoft Well-Known Member

    Регистрация:
    15 ноя 2005
    Сообщения:
    735
    Симпатии:
    0
    Если верить ссылке, то
    Так что без разницы сколько там функций - вопрос сколько памяти может быть занято по максимуму.

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

Поделиться этой страницей