float func1 (float *dP)
{
float F=0;
for(int n=0;n<16;n++)
F+=dP[n]*dP[n];
f/=16;
return(F);
КАК ПОСЧИТАТЬ ЁМКОСТНУЮ СЛОЖНОСТЬ?
Подскажите, пожалуйста, что такое емкостная сложность и как её расчитать в Си. Как я понял, это размер памяти, занимаемый программой, но ведь это не просто сумма размеров переменных.
Спасибо!
Если надо, могу программу выложить.
Спасибо!
Если надо, могу программу выложить.
Цитата:
Originally posted by OOMPH
Подскажите, пожалуйста, что такое емкостная сложность и как её расчитать в Си. Как я понял, это размер памяти, занимаемый программой, но ведь это не просто сумма размеров переменных.
Спасибо!
Если надо, могу программу выложить.
Подскажите, пожалуйста, что такое емкостная сложность и как её расчитать в Си. Как я понял, это размер памяти, занимаемый программой, но ведь это не просто сумма размеров переменных.
Спасибо!
Если надо, могу программу выложить.
Ну во-первых.Я не знаю какую именно ёмкостную сложность тебе сказали вычислить, бывают разные типы, зависящие от выбора едениц, а также критериев подсчёта. Самый простой вариант выглядит так : пусть переменная (числовая) занимает C байт (можно взять,конечно, конкретные велечины для int float итд, ведь они известны) , тогда максимальная ёмкостная сложность программы будет равна числу байт(едениц), которое занимают все переменные (n*C), а также + некоторому числу Z = max { exp1,exp2,exp3}; где exp 1...n - это выражения. Пример:
y = 2 + 1; // занимает такое выражение 2 у.е. памяти (допускаем, что число едениц памяти равно числу переменных). Ну, вот считаешь для всех выражений, находишь этот максимум, прибавляешь к памяти переменных. Затем если у тебя есть структуры - там аналогично. Если есть функции - тоже аналогично, плюс ещё память для каждого аргумента функции. Самый грубый подсчёт выглядит именно так, а вообще -то каждый препод по-своему любит, проверено :)
Как бы это чуть-чуть поподробнее...
Допустим, есть функция
То в этом случае у нас будет выделяться память под переменные F, n и массив dP соответственно 8, 2 и 8 байт.
Допустим, есть функция
Код:
То в этом случае у нас будет выделяться память под переменные F, n и массив dP соответственно 8, 2 и 8 байт.
Цитата:
Самый грубый подсчёт выглядит именно так
А это как нибудь записывается (ну, формулы какие-нибудь).
Цитата:
а вообще -то каждый препод по-своему любит, проверено
А когда препод сам не знает как это делать, а просит других, правда, если посчитаю, курсовик автоматом поставит:)
Помоги, плиз.
Цитата:
Originally posted by OOMPH
Как бы это чуть-чуть поподробнее...
Допустим, есть функция
То в этом случае у нас будет выделяться память под переменные F, n и массив dP соответственно 8, 2 и 8 байт.
А это как нибудь записывается (ну, формулы какие-нибудь).
А когда препод сам не знает как это делать, а просит других, правда, если посчитаю, курсовик автоматом поставит:)
Помоги, плиз.
Как бы это чуть-чуть поподробнее...
Допустим, есть функция
Код:
float func1 (float *dP)
{
float F=0;
for(int n=0;n<16;n++)
F+=dP[n]*dP[n];
f/=16;
return(F);
{
float F=0;
for(int n=0;n<16;n++)
F+=dP[n]*dP[n];
f/=16;
return(F);
То в этом случае у нас будет выделяться память под переменные F, n и массив dP соответственно 8, 2 и 8 байт.
А это как нибудь записывается (ну, формулы какие-нибудь).
А когда препод сам не знает как это делать, а просит других, правда, если посчитаю, курсовик автоматом поставит:)
Помоги, плиз.
Короче, функцию резидентно чтоли посчитать нужно ?
ну смари...
float* DP - 1 уе
F - 1уе
for(int n=0;n<16;n++) - вот это вот 2 уе всё вместе, однако если понимать под n++ n = n+1, то будет больше :)
dP[n]*dP[n] - 4 уе
16 - 1 уе
n - 1 уе
ретёрн(f) - допустим что 1 уе
зы: массив DP находится вне функции, его не считаем.
Это теоретический подсчёт разумеется, но он используется.
Цитата:
Originally posted by Darien
Короче, функцию резидентно чтоли посчитать нужно ?
ну смари...
float* DP - 1 уе
F - 1уе
for(int n=0;n<16;n++) - вот это вот 2 уе всё вместе, однако если понимать под n++ n = n+1, то будет больше :)
dP[n]*dP[n] - 4 уе
16 - 1 уе
n - 1 уе
ретёрн(f) - допустим что 1 уе
зы: массив DP находится вне функции, его не считаем.
Это теоретический подсчёт разумеется, но он используется.
Короче, функцию резидентно чтоли посчитать нужно ?
ну смари...
float* DP - 1 уе
F - 1уе
for(int n=0;n<16;n++) - вот это вот 2 уе всё вместе, однако если понимать под n++ n = n+1, то будет больше :)
dP[n]*dP[n] - 4 уе
16 - 1 уе
n - 1 уе
ретёрн(f) - допустим что 1 уе
зы: массив DP находится вне функции, его не считаем.
Это теоретический подсчёт разумеется, но он используется.
То есть получается, что на эту функцию уходит 1+1+2+4 уе. И так считать все функции в программе и суммировать?
А что за уе? Байты? Почему на float и на int одинаково по 1 уе?
А массив dP[16] находится в main'e, там и считаем.
Цитата:
Originally posted by OOMPH
То есть получается, что на эту функцию уходит 1+1+2+4 уе. И так считать все функции в программе и суммировать?
А что за уе? Байты? Почему на float и на int одинаково по 1 уе?
А массив dP[16] находится в main'e, там и считаем.
То есть получается, что на эту функцию уходит 1+1+2+4 уе. И так считать все функции в программе и суммировать?
А что за уе? Байты? Почему на float и на int одинаково по 1 уе?
А массив dP[16] находится в main'e, там и считаем.
Нет, не байты, а условные еденицы. Если длинное выражение то как для него байты считать ? Поэтому применяется такая система. Ну а float & int они ведь и так равны - 32 бита каждый.
Да, вот именно так все функции. Ещё раз повторюсь ёмкость = переменные + максимум из выражений.
Я тебя уже замучел, но ещё пара вопросов :)
ТУТ есть пример расчета сложности алгоритма, правда не на Си.
ТУТ есть пример расчета сложности алгоритма, правда не на Си.
Цитата:
Емкостная сложность:
В программе используется одномерный массив размерности n, поэтому объём
входа и объём выхода совпадают и равны n. Количество пременных равно
3(i,b,k) + 1(const n), т.е. объём промежуточных данных равен 4.
С(n)=n+4
В программе используется одномерный массив размерности n, поэтому объём
входа и объём выхода совпадают и равны n. Количество пременных равно
3(i,b,k) + 1(const n), т.е. объём промежуточных данных равен 4.
С(n)=n+4
Скажи пожалуйста, что такое объём
входа и объём выхода, как будет выглядеть в моём примере С(n)?
Записать, что в данной функции С(n)=11 ?
Цитата:
Originally posted by OOMPH
Я тебя уже замучел, но ещё пара вопросов :)
ТУТ есть пример расчета сложности алгоритма, правда не на Си.
Скажи пожалуйста, что такое объём
входа и объём выхода, как будет выглядеть в моём примере С(n)?
Записать, что в данной функции С(n)=11 ?
Я тебя уже замучел, но ещё пара вопросов :)
ТУТ есть пример расчета сложности алгоритма, правда не на Си.
Скажи пожалуйста, что такое объём
входа и объём выхода, как будет выглядеть в моём примере С(n)?
Записать, что в данной функции С(n)=11 ?
Прочитал твой линк :) Да просто всё: объём входа - это то, что мы как раз передаём в функцию, в твоём случае это тот массив dp ) Ну а выхода объём - это объём той структуры, в которую записывается результат алгоритма, в твоём случае это F.
ps : метод верификации Хоара в той статье используется(доказательство алгоритма), ну надо же :)
Цитата:
...объём
входа и объём выхода совпадают и равны n.
Количество пременных равно
3(i,b,k) + 1(const n), т.е. объём промежуточных данных равен 4.
С(n)=n+4
входа и объём выхода совпадают и равны n.
Количество пременных равно
3(i,b,k) + 1(const n), т.е. объём промежуточных данных равен 4.
С(n)=n+4
Растолкуй, пожалуйста, ещё один момент, желательно поподробнее и, если можно, на моём примере..(Дело в том, что сам то я пишу на php, а Си знаю где-то на уровне второго курса+сам полкниги прочитал(пока), поэтому расчет емкостной сложности для меня оказался большим сюрпризом. :o да и метод верификации Хоара мне, к сожаленью, ни о чем не говорит. В нете я помощи нигде не нашел, последняя надежда на тебя:roll:)
Так вот. Почему С(n)? То есть я должен получить ответ в виде выражения С(n)= n + Y, где, как я понял, Y - это все наши уе, а что такое n?
[SIZE=1]Вообще, до меня начало всё это потихоньку доходить, вот только про это информации маловато... :x
Я бы тебе за оказанную помощь ящик пива по почте прислал, вот только я думаю, ты сам знаешь, как в России почта работает, глядишь, через полгода дойдет(пустой :D )
[/SIZE]
Цитата:
Originally posted by OOMPH
Растолкуй, пожалуйста, ещё один момент, желательно поподробнее и, если можно, на моём примере..(Дело в том, что сам то я пишу на php, а Си знаю где-то на уровне второго курса+сам полкниги прочитал(пока), поэтому расчет емкостной сложности для меня оказался большим сюрпризом. :o да и метод верификации Хоара мне, к сожаленью, ни о чем не говорит. В нете я помощи нигде не нашел, последняя надежда на тебя:roll:)
Так вот. Почему С(n)? То есть я должен получить ответ в виде выражения С(n)= n + Y, где, как я понял, Y - это все наши уе, а что такое n?
[SIZE=1]Вообще, до меня начало всё это потихоньку доходить, вот только про это информации маловато... :x
Я бы тебе за оказанную помощь ящик пива по почте прислал, вот только я думаю, ты сам знаешь, как в России почта работает, глядишь, через полгода дойдет(пустой :D )
[/SIZE]
Растолкуй, пожалуйста, ещё один момент, желательно поподробнее и, если можно, на моём примере..(Дело в том, что сам то я пишу на php, а Си знаю где-то на уровне второго курса+сам полкниги прочитал(пока), поэтому расчет емкостной сложности для меня оказался большим сюрпризом. :o да и метод верификации Хоара мне, к сожаленью, ни о чем не говорит. В нете я помощи нигде не нашел, последняя надежда на тебя:roll:)
Так вот. Почему С(n)? То есть я должен получить ответ в виде выражения С(n)= n + Y, где, как я понял, Y - это все наши уе, а что такое n?
[SIZE=1]Вообще, до меня начало всё это потихоньку доходить, вот только про это информации маловато... :x
Я бы тебе за оказанную помощь ящик пива по почте прислал, вот только я думаю, ты сам знаешь, как в России почта работает, глядишь, через полгода дойдет(пустой :D )
[/SIZE]
Вообще-то правильно, но выражение C(n) подразумевает зависимость ёмкости от длины входных данных. А это возможно тока в 2х случаях : динамическое выделение памяти (что в примере твоём не имеет место быть) и 2) это переменная память для переменных - это вообще теоретическая вещь, ибо в С++ для всех типов память фиксирована, а в данном методе у нас память выделяется исходя из велечины числа, например число 8 бы занимало
log8 бит, тобишь 3 ). В твоём примере память у нас фиксирована и не зависит от входа.
Цитата:
Originally posted by Darien
Вообще-то правильно, но выражение C(n) подразумевает зависимость ёмкости от длины входных данных. А это возможно тока в 2х случаях : динамическое выделение памяти (что в примере твоём не имеет место быть) и 2) это переменная память для переменных - это вообще теоретическая вещь, ибо в С++ для всех типов память фиксирована, а в данном методе у нас память выделяется исходя из велечины числа, например число 8 бы занимало
log8 бит, тобишь 3 ). В твоём примере память у нас фиксирована и не зависит от входа.
Вообще-то правильно, но выражение C(n) подразумевает зависимость ёмкости от длины входных данных. А это возможно тока в 2х случаях : динамическое выделение памяти (что в примере твоём не имеет место быть) и 2) это переменная память для переменных - это вообще теоретическая вещь, ибо в С++ для всех типов память фиксирована, а в данном методе у нас память выделяется исходя из велечины числа, например число 8 бы занимало
log8 бит, тобишь 3 ). В твоём примере память у нас фиксирована и не зависит от входа.
В данном случае тогда емкость будет равна сумме условных единиц, то есть С=11, так?
А это нормальная форма записи емкости, или это на словах, а записывается всё это как-то иначе, просто мне это нужно ещё и оформить...?
Цитата:
Originally posted by OOMPH
В данном случае тогда емкость будет равна сумме условных единиц, то есть С=11, так?
А это нормальная форма записи емкости, или это на словах, а записывается всё это как-то иначе, просто мне это нужно ещё и оформить...?
В данном случае тогда емкость будет равна сумме условных единиц, то есть С=11, так?
А это нормальная форма записи емкости, или это на словах, а записывается всё это как-то иначе, просто мне это нужно ещё и оформить...?
Это вполне формально , если это оговорено у тебя в введении к твоей работе :)
Цитата:
Originally posted by Darien
Это вполне формально , если это оговорено у тебя в введении к твоей работе :)
Это вполне формально , если это оговорено у тебя в введении к твоей работе :)
В том то и дело, что это работа не моя, а преподавателя по электронике (это она пишет работу, а язык не знает):) Она дала мне прогу на 5 листов и "литературу", если это можно так назвать :) Щас сфоткаю.... Вот, рисунок, 70 килограмм.
Что-то я это ещё раз прочитал, и опять запутался...:x С одной стороны, там написано С=Сумма Тип*размер, с другой стороны дано C(n) для разных типов структур...
Цитата:
Originally posted by OOMPH
В том то и дело, что это работа не моя, а преподавателя по электронике (это она пишет работу, а язык не знает):) Она дала мне прогу на 5 листов и "литературу", если это можно так назвать :) Щас сфоткаю.... Вот, рисунок, 70 килограмм.
Что-то я это ещё раз прочитал, и опять запутался...:x С одной стороны, там написано С=Сумма Тип*размер, с другой стороны дано C(n) для разных типов структур...
В том то и дело, что это работа не моя, а преподавателя по электронике (это она пишет работу, а язык не знает):) Она дала мне прогу на 5 листов и "литературу", если это можно так назвать :) Щас сфоткаю.... Вот, рисунок, 70 килограмм.
Что-то я это ещё раз прочитал, и опять запутался...:x С одной стороны, там написано С=Сумма Тип*размер, с другой стороны дано C(n) для разных типов структур...
Ну что такое C(n) вообще ? это же функция, а функция от чего то зависеть должна, в данном случае от длины входа, но в твоей процедуре разве память зависит от длины входа ? конечно нет, так что не парься ты на этих символах просто :)