Literatürde bulunan bir çok farklı algoritmanın, farklı yazılım dillerinde implementasyonlarını yapmak mümkün. Bu algoritmaların koşacağı birbirinden farklı sistem kaynaklarının olduğunu düşündüğümüzde ise bu algoritmaların koştuğu sistem üzerindeki davranışını değil de, söz konusu olan algoritmanın karmaşıklığının maliyetini belirlemek için kullandığımız bir notasyon olan BIG-O notasyonunu bugün bir örnekle ele alacağım ve bu konuyu güzel bir şekilde ele alan bir udemy eğitiminden bahsedeceğim.
Çeşitli veri yapılarının ve operasyonların algoritma karmaşıklıklarına dair derli toplu bir yer arıyorsanız şuraya bakabilirsiniz.
Bugün şu soruyu irdeleyeceğiz,
N elemandan oluşan bir dizide negatif karşılığı bulunan tüm pozitif sayıları bulunuz.
Örneğin [2, 5, 1, -1 , -3, 7, 4 , -2] dizisi için sonuç [2, 1] olmalıdır.
Bu soru karşımıza bir mülakat esnasında gelebileceği gibi, bu tarz soruların üzerinde düşünmenin bizi daha dinç tuttuğunu düşünüyorum. Bu soruyu gördüğümüzde aklımızda hemen farklı yaklaşımlar belirebilir. Benim aklıma HackerRank sitesinde soruları çözerken kazandığım bir idiom gelmekte ve elemanların değerlerinin başka bir dizi üzerinde index olarak yapılandırması yolunu tercih ediyorum. Eğer daha önce HackerRank gibi platformlara göz gezdirmediyseniz ve problem çözmeyi seviyorsanız mutlaka bakın. Hem kodlama pratiği açısından oldukça güzel bir site hemde teknik mülakatlarda bulanacağımız zaman bize artı kattığını düşünüyorum uzun vadede.
Kodlamaya başlamadan önce size verilen veri setinden daha fazlasını düşünmek zorundasınız, yukarda gördüğünüz gibi 0’a tümleyen negatif sayıların mutlak karşılığı olan pozitif sayılar daha önce gelmekte. Kurduğunuz algoritma bunun tersi durumları handle edebiliyor mu ? Yine aynı şekilde yaklaşımınız mutlak değerleri eşit olan fakat aynı işaretli sayılar için nasıl davranıyor ? Benim yukarda bulunan soru için çözümüm bu şekilde oldu, eksik gördüğünüz noktalar ya da denediğiniz test durumları için yanlış bir sonuç verirse lütfen bilgilendirin. Eğer mobilden bu yazıyı okuyorsanız şuradan kodun biçimlendirilmiş haline ulaşabilirsiniz.
//NOT : SIZE verilen dizideki en yüksek değerden daha yüksek seçilmiştir.
#include <stdio.h>
#include <stdlib.h>
#define SIZE 10
const int test_array[SIZE] = {-2, 5, 1, -1, -3, -7, 7, 2, 3, 5};
int main(void) {
int emulate_array[SIZE] = { 0 };
for (int i = 0; i < SIZE; ++i)
{
//Dizide aynı sayının tekrarı olması durumu göz önünde alındı. Örnek dizi de -7 -7 ya da 5 5 gibi aynı ranka sahipse elenir.
if (test_array[i] < 0 && emulate_array[abs(test_array[i])] == 1)
{
printf("\r\n Bulundu = %d", abs(test_array[i]));
}
else if (test_array[i] > 0 && emulate_array[test_array[i]] == -1)
{
printf("\r\n Bulundu = %d", abs(test_array[i]));
}
if (test_array[i] > 0)
{
emulate_array[test_array[i]] = 1;
}
//Negatif sayi dizide daha önce gelebilir.
else
{
emulate_array[abs(test_array[i])] = -1;
}
}
return 0;
}
Sergilediğimiz bu yaklaşımı biraz daha irdeleyecek olursak, farkettiğiniz gibibellek kullanımı(space complexity) artmış durumda. Ve algoritmamızın karmaşıklığı şu anda O(n) durumunda ve bu hoş. Burada aklıma gelen ilk şey şu oldu bu yazdığım algoritma bir mikrodenetleyici içeren sistem üzerinde mi koşacak ? Yarın öbür gün veri setinin boyutunda gerçekleşebilecek bir artış benim donanımda kullandığım çipin tahsis edemeyeceği bir bellek boyutu durumuna gelebilir mi ? Farklı yaklaşımlar neler olabilir ve onların algoritma karmaşıklığının daha fazla olması fakat bellek kullanımının daha az olması sistemim için daha mı tercih edilebilir bir yöntem ? Veri setinin büyümesi sonucunda algoritma karmaşıklığı diğer sistemleri bloklar mı ? Bu ve benzer bir çok soru aklımıza gelebilir ve gelmesi önemli bence.
Anlatmaya çalıştığım gibi bu soruyu yapılabilecek farklı yaklaşım yöntemleri mevcut, belki öncesinde diziyi buble, quick sort gibi farklı maliyetlere sahip algoritmalar ile sıralayabilir ve sonrasında da işlem yapabilirsiniz. Benim yöntemim doğru diğer yaklaşımlar yanlış demek çok mümkün değil ve yanlış bir bakış açısı olur.
Yazının başında belirttiğim gibi bu konuları içerisinde barındıran henüz bitirmedim ama geldiğim noktaya kadar yeni şeyler öğrendiğim ve mevcut öğrendiklerimi tazelediğim bir udemy eğitiminin promosyonlu linkine buradan erişebilirsiniz. Bir eğitim alırken dikkat ettiğim bir konu var, ben tecrübeye para ödemeyi seçiyorum, zira udemy üzerinde internet üzerinden topladığı bilgileri henüz kendi süzgecinden geçirmeden paylaşan bir çok birey var. Bu bana çok doğru gelmiyor. Eğitim linkini bıraktığım videoları hazırlayan kişilerin hem kendileri aday pozisyonunda hemde adayları değerlendirdiği bir pozisyonda bulunduğunu düşünürsek kazandıkları deneyimler için bu kadar cüzzi bir miktar ödemek bence çok iyi. Eğer öğrenciyseniz ve bu eğitimi almak bütçeniz için uygun değilse benimle .edu uzantılı mail adresinizden iletişime geçebilirsiniz.
Kolaylıklar dilerim.
Volkan's Space 