Здравейте,

Погледнах видео за определяне на сложността на алгоритъм в което има пример с цикъл

void func(int items[], n)
{
	int  sum = 0;
	
	for(int i=0;i<n;i++)
    {
		sum = sum + items[i];                 
    }

}

Защо при него броят на инструкции е 6n+3?

Аз ги броя, че има първо за заделяне на памет за променливата 1 и за асайнмент още 1. След това в цикъла създаване и иницализиране на променливата i общо 2 и n-пъти сравняване с n, и при следващата итерация n пъти инкрементиране (i++). В тялото на цикъла има 1 инструкция за асайнмент 1 за събиране и още 1 за достъпване на елемента.

Как работи това броене? 

 

преди 5 минути, frozener написа:

Здравейте,

Погледнах видео за определяне на сложността на алгоритъм в което има пример с цикъл

Защо при него броят на инструкции е 6n+3?

Аз ги броя, че има първо за заделяне на памет за променливата 1 и за асайнмент още 1. След това в цикъла създаване и иницализиране на променливата i общо 2 и n-пъти сравняване с n, и при следващата итерация n пъти инкрементиране (i++). В тялото на цикъла има 1 инструкция за асайнмент 1 за събиране и още 1 за достъпване на елемента.

Как работи това броене? 

 

Не знам от къде сте намерил тези метрики, но при по-общите метрики този алгоритъм има сложност n. Дали е 1*n, 100*n няма значение, все е n

Окей за по-общия случай, обаче кое считат за инструкция и как броят инструкциите? Също така как примерно се стига до извод, че даден алгоритъм има сложност логаритъм от n или нещо подобно с логаритми. Наясно съм, че съществува worst case, average и best case и асимптотното поведение, но не ми е ясно как се брои.

преди 2 минути, frozener написа:

Окей за по-общия случай, обаче кое считат за инструкция и как броят инструкциите? Също така как примерно се стига до извод, че даден алгоритъм има сложност логаритъм от n или нещо подобно с логаритми. Наясно съм, че съществува worst case, average и best case и асимптотното поведение, но не ми е ясно как се брои.

По кой метод. Има различни методи: https://en.wikipedia.org/wiki/Analysis_of_algorithms

на Tuesday, October 11, 2016 в 19:56, capnemo написа:

По кой метод. Има различни методи: https://en.wikipedia.org/wiki/Analysis_of_algorithms

Еми ако говорите за функция тогава става дума за Big O. За нея знам, че  константите се махат, защото те не се променят спрямо големината на входните данни и че показва worst case, обаче не знам примерно как се определя n log n или log n при броенето на инструкции в цикли.

Примерно

for(int i =0;i<n;i++)

{

      n = n / 2;

      counter++;

}

Това трябва да има log n според един лектор обаче не ми е ясно защо не се брои и counter понеже той n пъти ще се изпълнява.

Редактирано 14 октомври 20169 г. от frozener (преглед на промените)

преди 37 минути, frozener написа:

 обаче не ми е ясно защо не се брои и counter понеже той n пъти ще се изпълнява.

В контекста, тази (big O) нотация показва промяната на определено изискване (време на изпълнение, необходима памет) на алгоритъма, като функция на n, а не абсолютното време за изпълнение...

Тоест, два различни алгоритъма със сложност по време log(n) може да се изпълняват за произволно различно време при едно и също n.

П.П. погледнато от някаква гледна точка, може и да се каже, че counter++ се изпълнява n пъти, ама това е изказване на политик, честно ти казвам... Или на Реджеп, той ги е измислил тия работи (политиката имам предвид)

преди 37 минути, frozener написа:

 че показва worst case,

П.П.2 това не е вярно. Може да показва (и се използва за да показва), който case искаш. Просто някои алгоритми имат различни стойности за най-добър/среден/най-лош случай.

Редактирано 14 октомври 20169 г. от flare (преглед на промените)

преди 52 минути, frozener написа:

Еми ако говорите за функция тогава става дума за Big O. За нея знам, че  константите се махат, защото те не се променят спрямо големината на входните данни и че показва worst case, обаче не знам примерно как се определя n log n или log n при броенето на инструкции в цикли.

Примерно

for(int i =0;i<n;i++)

{

      n = n / 2;

      counter++;

}

Това трябва да има log n според един лектор обаче не ми е ясно защо не се брои и counter понеже той n пъти ще се изпълнява.

на ръка изпълнете цикъла и вижте колко пъти се изпълнява при различни стойности на n. Не забравяйте че вие променяте вътре в цикъла максималната стойност на брояча