Yapay zekadan makale özeti
- Kısa
- Ayrıntılı
- Bu video, bir eğitmen tarafından sunulan insertion sort (araya sokma sıralaması) algoritması hakkında kapsamlı bir eğitim içeriğidir.
- Video, algoritmanın çalışma prensibini iskambil kartları örneği üzerinden açıklayarak başlıyor, ardından sözde kodu inceleniyor ve son olarak maliyet ve zaman analizi yapılıyor. Eğitmen, algoritmanın en iyi durumda O(n), ortalama durumda O(n) ve en kötü durumda O(n²) karmaşıklığında çalıştığını matematiksel olarak gösteriyor.
- Videoda ayrıca tersten sıralı bir dizide insertion sort'un en kötü durumda nasıl çalıştığı ve bu durumda algoritmanın zaman karmaşıklığının nasıl hesaplanacağı adım adım gösteriliyor. Bu içerik, algoritma öğrenmek isteyenler için temel bir kaynak niteliğindedir.
- 00:01Insertion Sort Algoritması Tanıtımı
- Insertion Sort algoritması, sıralı bir dizeye yeni bir eleman eklemeyi temsil eder.
- Algoritmanın çalışma mantığı, sıralı bir dizeye yeni bir elemanı doğru yere yerleştirmektir.
- Örnek olarak, sıralı bir iskambil kart dizisine yeni bir kartı doğru yere yerleştirmek gibi çalışır.
- 00:59Insertion Sort Algoritmasının Çalışma Örneği
- Sırasız bir dizide, ilk eleman (25) zaten sıralı olduğu için birinci indeksten başlanır.
- İkinci eleman (12) 25'ten küçük olduğu için yer değiştirilir ve dizinin doğru sırasına yerleştirilir.
- Üçüncü eleman (7) dizinin başına yerleştirilirken, 25 ve 12'ye karşı karşılaşıp yer değiştirir.
- 03:24Insertion Sort Algoritmasının Çalışma Mantığı
- Algoritma, "araya sokma sıralaması" olarak da adlandırılır.
- Sudo kodunda, dizi uzunluğundan (n) başlayarak, her eleman kenara alınır ve doğru yere yerleştirilir.
- İçteki while döngüsü, elemanı doğru yere yerleştirmek için sol taraftaki elemanlarla karşılaştırılır.
- 05:46Insertion Sort Algoritmasının Zaman Karmaşıklığı
- Her işlemin bir maliyeti vardır ve bu maliyetler c1, c2, c3, c4, c5, c6, c7, c8 şeklinde gösterilir.
- For döngüsü n kere, for döngüsünün içindeki işlemler n-1 kere çalışır.
- En iyi durumda (best case), dizinin zaten sıralı olması durumunda, her eleman için sadece bir kontrol yapılarak yerleştirilir.
- 08:29En İyi Durum Zaman Karmaşıklığı
- En iyi durumda (best case), dizinin zaten sıralı olması durumunda, her eleman için sadece bir kontrol yapılır.
- Denklemi çözdüğümüzde, T(n) = an + b şeklinde bir formül elde edilir.
- En iyi durumda çalışma zamanı O(n) karmaşıklığına sahiptir.
- 10:14En Kötü Durumda Insertion Sort Zaman Karmaşıklığı
- En kötü durumda, tersten sıralı bir dizide her gelen yeni elemanda j kadar soluna kontrol etmek gerekecek.
- Her gelen elemanda sol tarafa bakarak sürekli tersine işlem yapacağı için T(C) değeri j olacak.
- En kötü durumda, while döngüsü j kadar, while içindeki kod j-1 kadar çalışacak.
- 11:13Matematiksel Hesaplamalar
- Toplam sembolü ile iki'den n'e kadar sayıların toplamı n×(n+1)/2-1 olarak hesaplanıyor.
- j=2'den n-1'e kadar olan sayıların toplamı n×(n-1)/2 olarak hesaplanıyor.
- Bu hesaplamalar yapılarak formülün son hali a×kare+b×c olarak bulunuyor.
- 12:19Sonuç
- En büyük katsayılı terim n kare olduğu için zaman karmaşıklığı O(n²) olarak belirleniyor.
- Ortalamada m/2 olacağı için en kötü durumda olduğu gibi O(n²) zaman karmaşıklığına sahip olacak.