Amaçlarımız:

*Yalnızca değiştokuş(i,j) ve elemanların sıra ilişkisini (<) kullandığımız öyle bir yöntem bulmak ki sonunda verilen kümedeki elemanlar tümüyle artan sıraya girmiş olsun. Matematiksel deyişle: Bütün i,j ler için xi < xj ise i < j dir.
(Yani, amaç defterdeki bütün sözcükleri, ikili değiştokuşlarla, artan sıraya sokmak)

*Yöntemde kullanılan değiştokuş(i,j) işlemlerinin 'en az' olmasını sağlamak. Bu 'en az' değiştokuş(i,j) sayısını N cinsinden tarif etmek.

Büyük olasılıkla bazı çözümleri kafanızda oluşturdunuz bile. Çözümünüzü irdelediğinizde, verilerin en kötü sıralanışlarında bile yönteminizin en fazlası ile K adet değiştokuş(i,j) işlemi yaparak amacı sağladığını saptadınız. İlk akla gelen çözümler çoğunlukla K=N×(N+1)/2 adet değiştokuş(i,j) gerektirirler. Bu bağımlılığın derecesine 'mertebe' diyoruz. Yani ilk akla gelen (büyük olasılıkla sizin de bulduğunuz) çözümler N2mertebesindedir. Peki en iyi yöntem için bu 'mertebe' nedir diye merak edenler için yanıtı verelim: N×log(N). Verilmiş kurallar çerçevesinde, herhangi bir yöntemin bundan daha iyi bir başarıda olamayacağının tanıtı (ispatı) da Bilgisayar Biliminde mevcut.

Bu arada yeri gelmişken şunu da belirtelim: Bilgisayar Biliminde bu tür yöntemlere 'Algoritma' diyoruz. Merak edenler için: Algoritma sözcüğü, matematiksel olarak bazı cebir işlemlerini bir yöntem olarak betimleyen, 9 Asırın başında yaşamış Acem asıllı matematik bilgini Abu Cafer Muhammed İbn-Musa-Al-Khovarizmi'in adından gelmektedir. Al-Khovarizmi Farsça 'Harzemli' demektir.

Hiç yorum yok: