Поиск максимума и минимума

Atlantic

Код (Text):

1.  for(i=M;i<N;i++)    //O(N)
2.     {
3.         if(i%M==0)
4.         {
5.             m=a[i-1];
6.             for(j=1;j<=M;j++)
7.             {
8.                 if(a[i-j]<m)
9.                     m=a[i-j];
10.                 b[M-j]=m;
11.             }
12.             m=a[i];
13.         }
14.         if(a[i]<m)
15.             m=a[i];
16.         printf("%2d ",b[i%M]<m?b[i%M]:m);
17.     }

в этом коде массив b просто заполняется на этом его использование оканчивается, так что он бажный.
из твоего описания я понял следующее, поправь меня, коли я не прав, плзззззззззз: идёт сравнение текущего элемента с текушим минимумом в окне, а потом с минимумом за пределами окна.
---------------------------------
СПАСИБО ЗА ОПИСАНИЕ.
Чёрное_Зеркало
Код и впрямь ГЕНИАЛЕН -у тебя талант займись факторизацией - ты решишь эту задачу, потом расскажи, мне - ламеру, ПЛЗЗЗЗЗЗЗЗ

 

Он используется: printf("%2d ",b[i%M]<m?b[i%M]:m);

Окно разбивается на две части: та, что попадает в массив b, и та, что в него не попадает (минимум по этой части - число m).

 

Atlantic

точно:-D - не доглядел

 

попытался реализовать стратегию ведущий/ведомый: один массив юзается - другой заполняется, но колво операций не уменьшилось. Чемпион, по всей видимости, идеален.

 

Black_mirror, ты просто гений!

Miller Rabin
см. #102, там увидишь и свой алг, и его приблизительную оценку в числах
если без чисел, то получается O(N*log2(k))