Elimizde N boyutlu bir küme olsun. Bu kümenin K boyutlu altkümelerinden en küçük standart sapmaya ait olanını nasıl buluruz?

İnsanın ilk olarak aklına K eleman sayılı tüm altkümeleri sırasıyla denemek geliyor. Bunu nchoosek ile yapabiliriz. 

N = 20;
K = 10;
x = rand(N,1);
C = nchoosek(x, K);

tic
min_s = realmax;
for i = 1:size(C,1)
    s = std(C(i,:));
    if s < min_s
        min_s = s;
        en_iyi_C = C(i,:);
    end
end
toc

Benim bilgisayarımda 8.33 s tuttu:

Elapsed time is 8.329337 seconds.

Altküme sayısı $\frac{20!}{10!\times 10!} = 184756$. Küçük bir sayı. Peki N 100 olsaydı, K da 50 olsaydı ne yapacaktık? Altküme sayısı $\frac{100!}{50! \times 50!} = 100891344545564150000000000000$ olacaktı. Bir hayli (!) büyük bir sayı. Buna hafıza yetmez dediğinizi duyuyorum. Evet, buna bilgisayardaki beyin yetmez. Ama bizde beyin bedava, onu kullanalım.

Önce elemanları sıralayalım:

N = 100;
K = 50;
x = rand(N,1);
tic
[x_s, ind] = sort(x);

Şimdi de her K boyutlu ardışık dizilimde standart sapmayı hesaplayalım. 

min_s = realmax;
for i = 1:(N-K+1)
    s = std(x_s(i:(i+K-1)));
    if s < min_s
        min_s = s;
        en_iyi_ind = ind((i:(i+K-1)));
    end
end
toc

Algoritmamız bu kadar. Sıralamanın karmaşıklığı $O(N \log N)$, sonraki döngü $O(NK)$. Sonuçta karmaşıklık bunların küçüğü.

Artık 1000 elemanlı bir kümenin 500 elemanlı en düşük standart sapmaya ait altkümesini hesaplamak 0.070 s sürüyor!