сложность алгоритма

[NiCola999]

задача о размене монет с номиналами 25,10,5,1 вот алгоритм

coins = [25,10,5,1]
N = 78
k=N
while k > 0
       while i < coins.size
	      if coins[i] <= k
	        max = coins[i]
		    break
		  end
		i+=1		
	   end
	  razmen[i] = max		  				   		  		          		   
	  k-=max   
end

Берется число N которое надо разменять, находится монета с наибольшим номиналом, но не больше N, кладется в массив razmen,
затем из N вычитается номинал этой монеты. Таким образом получается размен монет

Пример:

a = [25,10,5,1]
n = 78
razmen[i] = max(a) = 25
n=n-25 = 52
razmen[i] = max(a) = 25
n=n-25 = 27
razmen[i] = max(a) = 25
n=n-25 = 2
razmen[i] = max(a) = 1
n=n-25 = 1
razmen[i] = max(a) = 1
n=n-25 = 0
razmen[i] = max(a) = 1

нужно вычислить сложность алгоритма.

кол-во итераций вложенного цикла всегда равно coins.size-1 = 3
как расчитать зависимость от N кол-во итераций первого цикла ?

[LeBron]

Зачем ерундой голову себе забивать? Сделать одним общим формализатором и все. Тогда сложность равна количеству монет, которые входят в итоговый размен. А если не сохранять сами монеты, а только количество, то алгоритм O(1).

[NiCola999]

дело в том, что в задании сказано использовать жадный алгоритм, вот я его и написал.

допустим I кол-во итераций первого цикла, тогда получается
a = [25,10,5,1]

I = Sum(k=N, 0 ) k /= max(a[k])

max(a[k]) = максим номинал монеты, который не больше k

как теперь вычислить сложность всего алгоритма ?

[LeBron]

Так и пишите жадный алгоритм. Только по-человечески, по принципу

if n>=25 then begin 
for t:=1 to n div 25 do begin inc(i);ar[i]:=25;end;
n:=n mod 25;end;

З.Ы. Для больших чисел количество итераций примерно равно количеству монет, а количество монет стремиться к n/25.

[NiCola999]

я паскаль не знаю, что это значит?
for t:=1 to n div 25 do begin inc(i);ar[i]:=25;end;

цикл от 1 до n/25
a[i] = 25
i+=1
?

количество монет стремиться к n/25

n = 78, хочешь сказать что кол-во монет будет стремиться к 3 ?

[LeBron]

Сообщение от NiCola999

я паскаль не знаю, что это значит?
for t:=1 to n div 25 do begin inc(i);ar[i]:=25;end;

цикл от 1 до n/25
a[i] = 25
i+=1
?

То же самое на плюсах:

if (n>=25){
for (t=1;t<=n/25;t++){i++;ar[i]=25;}
n%=25;}

Я показал пример для монет по 25. Для остальных дальше так же. Суть такая - считаем, сколько монет по 25 можно "отнять" и отнимаем их одним циклом, не проверяя каждый раз, можно ли еще забирать 25, или уже нечего забирать.

[NiCola999]

так у меня получается тоже самое что и у тебя, просто вместо 25 идут элменты массива.Только кол-во итераций получается 3+кол-во монет

[LeBron]

Сообщение от NiCola999

так у меня получается тоже самое что и у тебя, просто вместо 25 идут элменты массива. Кол-во итераций получается 3+кол-во монет в размене

По сути да, но мой вариант более общий - такое используют, если надо просто подсчитать количество монет, не разменивая. Или, например, если можно написать так: 12*25+4*10+1*5+2*1 В конкретно взятом случае да, оба решения одинаково хорошие.

[NiCola999]

так как расчитать O(n) ?=)

[LeBron]

Рассчитать - разложить? Это и есть решение за О(n). И Ваше, и мое решение, при увеличении числа N, скажем, с миллиона до 2 миллионов, станут работать в 2 раза дольше.