Veri Yapısında Arama: Açıklanan Farklı Arama Yöntemleri
Yayınlanan: 2021-05-03İletişim ağı genişliyor ve insanlar interneti kullanıyor! İşletmeler verimli yönetim için dijitalleşiyor. İnternette üretilen veriler artıyor ve bu nedenle veri kümeleri karmaşıklaşıyor. Verileri dikkatli ve verimli bir şekilde organize etmek, yönetmek, erişmek ve analiz etmek çok önemlidir, bir veri yapısı en yararlı tekniktir ve makale de buna odaklanmaktadır!
İçindekiler
Veri yapısı
Bilgisayar biliminde, veri yapıları, ADT'nin veri türünün mantıksal biçimi olduğu soyut veri türlerinin (ADT) temelidir. Veri türünün fiziksel düzeni, veri yapısı kullanılarak uygulanır. Farklı uygulama türleri için farklı veri yapısı türleri kullanılır; bazıları belirli görevlerde uzmanlaşmıştır.
Veri yapısı, veri değerleri ve bunlar arasındaki ilişkiler, verilere uygulanabilir işlemler ve işlevler topluluğudur. Verileri belirli bir biçimde düzenlemeye, yönetmeye ve depolamaya yardımcı olur. Böylece, kullanıcılar verilere kolayca erişebilir ve verimli bir şekilde değiştirebilir.
Veri yapıları, büyük veritabanları gibi büyük miktarda verinin yönetilmesine yardımcı olur. Verimli veri yapılarına dayalı olarak verimli algoritmalar oluşturulur. Verimli depolamanın yanı sıra, veri yapıları, saklanan bellekten bilgilerin verimli bir şekilde alınmasından da sorumludur. Bir dizi, Bağlantılı Liste, İşaretçi, Arama, Yığın, Grafik, Kuyruk, Yapı, Programlar, Sıralama ve benzerlerini içerir.
Makale, Veri Yapısında Arama kavramını ve yöntemlerini kapsar. Kavramı net bir şekilde anlamak için iki algoritma örneği ayrıntılı olarak açıklanmıştır. Daha fazla bilgi, beceri ve uzmanlık kazanmak için, makalenin sonunda belirtilen veri yapısı üzerine çevrimiçi kurslar mevcuttur.
Veri Yapısında Arama Nedir?
Bilgisayar belleğinde öğeler biçiminde depolanan öğeler kümesinden istenen bilgiyi bulma işlemine 'veri yapısında arama' denir. Bu öğe kümeleri dizi, ağaç, grafik veya bağlantılı liste gibi çeşitli biçimlerdedir. Veri yapısında aramayı tanımlamanın başka bir yolu, belirli özelliklerin istenen öğesini bir öğe koleksiyonunda bulmaktır.
Arama Yöntemleri
Veri yapısında arama, saklanan veri yapısının herhangi bir biçiminden bir öğeyi kontrol etmek veya almak için arama algoritmaları uygulanarak yapılabilir. Bu algoritmalar, arama işlemi türlerine göre kategorilere ayrılır, örneğin:
- sıralı arama
Dizi veya eleman listesi, kümenin her bileşeni kontrol edilirken sırayla geçilir.
Örneğin, Doğrusal Arama.
- Aralıklı Arama
Sıralanmış veri yapılarında arama yapmak için açıkça tasarlanmış algoritmalar, aralıklı aramaya dahil edilir. Bu algoritmaların verimliliği, doğrusal arama algoritmalarından çok daha iyidir.
Örneğin, İkili Arama, Logaritmik Arama.
Bu yöntemler, veri koleksiyonlarında arama öğesiyle eşleşen bir öğeyi aramak için bir algoritma tarafından geçen süreye göre incelenir ve aşağıdakiler tarafından verilir:
- mümkün olan en iyi zaman
- ortalama süre
- En kötü zaman
Birincil endişeler, algoritmanın performansının garantili tahminlerine yol açan ve ortalama sürelere kıyasla hesaplanması kolay olan en kötü durum süreleriyle ilgilidir.
Bu makaledeki örnekleri ve kavramları göstermek için, herhangi bir veri biçimindeki veri toplamadaki 'n' öğeleri dikkate alınır. Baskın işlemler, analizi ve algoritma karşılaştırmasını basitleştirmek için kullanılır. Bir veri yapısında arama yapmak için, O() ile gösterilen ve “büyük-Oh” veya “Oh” olarak telaffuz edilen karşılaştırma, baskın bir işlemdir.
Bir veri yapısında doğrusal arama, ikili arama, enterpolasyon arama, atlama arama, üstel arama, Fibonacci arama, alt liste arama, her yerde bulunan ikili arama, sınırsız ikili arama, alt dizi arama için özyinelemeli işlev ve özyinelemeli program gibi çok sayıda arama algoritması vardır. verilen dizide bir öğeyi doğrusal olarak aramak için. Makale, doğrusal ve ikili arama algoritmaları ve çalışma prensipleri ile sınırlıdır.
Veri yapısındaki doğrusal arama ve ikili arama hakkında ayrıntılı bilgi edinelim.
Doğrusal Arama
Doğrusal arama algoritması, dizideki tüm öğeleri sırayla arar. En iyi yürütme süresi birdir, en kötü yürütme süresi ise n'dir; burada n, arama dizisindeki toplam öğe sayısıdır.
Veri yapısındaki en basit arama algoritmasıdır ve öğe kümesindeki her öğeyi, veri toplamanın sonuna kadar arama öğesiyle eşleşene kadar kontrol eder. Veriler sıralanmadığında, doğrusal bir arama algoritması tercih edilir.
Doğrusal aramanın aşağıda verilen bazı karmaşıklıkları vardır:
- Uzay Karmaşıklığı
Doğrusal arama için uzay karmaşıklığı O(n)'dir, çünkü n'nin bir dizideki eleman sayısı olduğu herhangi bir fazladan boşluk kullanmaz.
- Zaman Karmaşıklığı
*En iyi durum karmaşıklığı = O(1), arama elemanı, arama dizisindeki ilk elemanda mevcut olduğunda oluşur.
*En kötü durum karmaşıklığı = O(n), arama öğesi öğe kümesinde veya dizide bulunmadığında oluşur.
*Ortalama karmaşıklık = O(n), öğe arama dizisinde bir yerde mevcut olduğunda belirtilir.
Örnek vermek,
Aşağıda verilen bir dizi eleman alalım:
45, 78, 12, 67, 08, 51, 39, 26
Yukarıda verilen 8 elemanlı bir dizide '51'i bulmak için, doğrusal bir arama algoritması, her bir elemanı, işaretçisi bellek alanında 51'i gösterene kadar sırayla kontrol edecektir. Bir dizide 51'i bulmak O(6) zaman alır. Yukarıdaki dizide 12'yi bulmak için O(3), 26 için ise O(8) zamanı gerekir.
Ikili arama
Bu algoritma, veri toplamadaki en ortadaki öğeleri karşılaştırarak belirli öğeleri bulur. Bir eşleşme gerçekleştiğinde, öğenin dizinini döndürür. Ortadaki öğe öğeden büyük olduğunda, sol alt dizinin merkezi öğesini arar. Buna karşılık, ortadaki öğe arama öğesinden daha küçükse, sağ alt dizideki öğenin ortasını araştırır. Bir öğeyi bulana kadar veya alt dizilerin boyutu sıfır olana kadar aramaya devam eder.
İkili arama, öğelerin sıralanmış düzenine ihtiyaç duyar. Doğrusal bir arama algoritmasından daha hızlıdır. Böl ve fethet prensibine göre çalışır.
Çalışma zamanı karmaşıklığı = O(log n)
İkili arama algoritmasının aşağıda verilen karmaşıklıkları vardır:
- En kötü durum karmaşıklığı = O (n log n)
- Ortalama karmaşıklık = O (n log n)
- En iyi durum karmaşıklığı = O (1)
Örnek vermek,
08 elemanlı sıralanmış bir algoritma alalım:
08, 12, 26, 39, 45, 51, 67, 78
Yukarıdaki elemanların bir dizisinde 51'i bulmak için,
Algoritma bir diziyi 08, 12, 26, 39 ve 45, 51, 67, 78 olmak üzere iki diziye böler.
51, 39'dan büyük olduğu için dizinin sağ tarafındaki öğeleri aramaya başlayacaktır.
Daha sonra 45, 51 ve 67, 78 gibi ikiye böler.
51, 67'den küçük olduğundan, o alt dizinin solunda aramaya başlayacaktır.
Bu alt dizi yine 45 ve 51 olarak ikiye ayrılır.
51, arama öğesiyle eşleşen sayı olduğundan, dizideki o öğenin dizin numarasını döndürür.
Arama elemanının 51 bir dizide 6. konumda yer aldığı sonucuna varacaktır.
İkili arama, karşılaştırma sayısı doğrusal arama algoritmasına göre önemli ölçüde azaltıldığı için süreyi yarıya indirir.
Okuyun: Python'da Veri Yapısı Türleri
İnterpolasyon Araması
İkili arama algoritmasının geliştirilmiş bir çeşididir ve arama öğesinin yoklama konumu üzerinde çalışır. İkili arama algoritmalarına benzer şekilde, yalnızca sıralanmış veri toplamada verimli çalışır.
En kötü yürütme süresi = O(n)
Veri toplamada hedef elemanın konumu bilindiğinde, bir enterpolasyon araması kullanılır. Telefon rehberinde bir numara bulmak için, Monica'nın telefon numarasını aramak isterse, lineer veya ikili arama kullanmak yerine, isimlerin 'M' ile başladığı hafıza alanı deposuna doğrudan araştırma yapılabilir.
Çözüm
Veri yapılarında arama yapmak, 'n' öğeler dizisinde belirli bir öğeyi bulmak anlamına gelir. İki kategori vardır, yani. Aramada sıralı arama ve aralıklı arama. Hemen hemen tüm arama algoritmaları bu iki kategoriden birine dayanmaktadır. Doğrusal ve ikili arama, ikili sistemin doğrusal algoritmalardan daha hızlı çalıştığı iki basit ve uygulaması kolay algoritmadır.
Doğrusal arama en basit olmasına rağmen, arama öğesiyle bir eşleşme bulana kadar her öğeyi kontrol eder, bu nedenle veri toplama doğru şekilde sıralanmadığında verimlidir. Ancak, veri toplama sıralanmışsa ve bir dizinin uzunluğu önemliyse, ikili arama daha hızlıdır.
Veri yapısı, veri kümeleriyle uğraşırken bilgisayar programlamanın önemli bir parçasıdır. Programcılar ve geliştiriciler, bilgisayar programlama tekniklerindeki temel bilgiler ve güncellemelerle kendilerini güncellemeye ve becerilerini geliştirmeye devam etmelidir. Veri yapısıyla uğraşan programcılar sıklıkla kursları tercih etmelidir.
Veri bilimi hakkında daha fazla bilgi edinmek istiyorsanız, çalışan profesyoneller için oluşturulan ve 10'dan fazla vaka çalışması ve proje, pratik uygulamalı atölye çalışmaları, endüstri uzmanlarıyla mentorluk sunan IIIT-B & upGrad'ın Veri Biliminde Yönetici PG Programına göz atın. Sektör danışmanlarıyla bire bir, en iyi firmalarla 400+ saat öğrenim ve iş yardımı.
