In: Genel


Bilgisayar Biliminde, herhangi bir program veya algoritmanın verimliliği, o algoritmanın Zaman ve Mekan Karmaşıklığı cinsinden ölçülür. Bu yazıda algoritmaların Zaman Karmaşıklığı hakkında konuşacağız ve bazı ortak zaman karmaşıklıklarına sahip farklı algoritmalara göz atacağız.

Bilgisayar biliminde Zaman Karmaşıklığı, sabit bir zamanda yürütülen temel işlemleri/ifadeleri yürütmek için gereken “hesaplamalı zaman” miktarı olarak ölçülür. Zaman karmaşıklığı genellikle Big O notasyonu ile gösterilir ve algoritma girişinin bir fonksiyonu olarak alınır.

Bunu daha iyi anlamak için, bazı programlara bir göz atalım:


long  NumberOfHandShakes(int persons_in_the_room)
{
long handshakes = (persons_in_the_room * (personss_in_the_room - 1)) / 2;
	return handshakes;
}


Bu fonksiyonda, odada bulunan herkesin odada bulunan diğer herkesle el sıkışması durumunda gerçekleşecek olan el sıkışma sayısını hesaplıyoruz. Bu fonksiyonun iki ifadesi vardır.

İlk ifade matematiksel bir ifadedir.


long handshakes = (persons_in_the_room * (personss_in_the_room - 1)) / 2;


hangi sabit bir sürede yürütülecektir.

İkinci ifade sonucu döndürür, bu nedenle sabit bir zamanda yürütülür.

Her iki ifadenin de 1 birim hesaplama zamanı aldığını düşünürsek, fonksiyonumuzun Zaman Karmaşıklığı O(2) olur.

Şimdi, girdinin boyutu ne olursa olsun (odadaki kişi sayısı ister 2 ister 758 olsun), bu fonksiyonun hesaplama karmaşıklığı her zaman aynı kalacaktır. Bu iki ifadeyi aynı sürede yürütecektir.

Hesaplama karmaşıklığının girdinin boyutundan bağımsız olduğu bu tür algoritmalar için, algoritmanın bir Sabit Zaman Karmaşıklığı ve her zaman olarak gösterilir O(1).

Sabit Zaman karmaşıklığının diğer örnekleri şunlardır:

  • Sayının Tek mi Çift mi olduğunu bulma
  • Bağlantılı Listeye düğüm ekleme
  • Bir yığından Push veya Pop işlevi

Logaritmik Zaman Karmaşıklığı

Şimdi ikili arama algoritmasına bir göz atalım. İkili Aramaya aşina olmayanlar için, bir “Sıralı Liste/Dizi” içindeki bir öğeyi aramak için bir algoritmadır. Her adımda dizinin ortasını buluyoruz ve elemanımızın orta indeksteki sayıyla eşleşip eşleşmediğini görüyoruz. Eğer öyleyse, indeksi elemanın bulunduğu konum olarak döndürürüz, aksi takdirde, elemanımızın ortadaki elemandan daha küçük veya daha büyük olmasına bağlı olarak, ortanın soluna veya ortanın sağına hareket ederiz.

Etkili bir şekilde, listeyi “her adımda yarıya” indiriyoruz, bu nedenle öğeyi bulmak için gereken adım sayısı, n’nin dizideki/listedeki öğelerin sayısı olduğu ve olarak belirtilir O(günlük n).


int BinarySearch(int[] a, int element)
{
	int start = 0, end = a.length() - 1;
	int mid;
	while (start < end)
	{
		mid = (start+end)/2;
		if( a[mid] == element)
			return mid;
		Elseif (a[mid] < element) start = start + 1; elseif(a[mid] > element)
			end = end - 1;
	}

	return -1;
}


Önemli

  • Şu anda, bu algoritmada bir dizi ifade olmasına rağmen, yalnızca öğeyi bulmak için atılan adımların sayısını dikkate aldığımızı düşünüyor olmalısınız. Başlangıçta tartışıldığı gibi, bu fonksiyonun zaman karmaşıklığını hesaplamak için, değişkenlerin atanması, orta, koşullu ifadelerin ve atama ifadelerinin hesaplanması gibi her ifadenin her birinin sabit bir zaman aldığını, yani her birinin 1 hesaplama birimi aldığını düşünüyoruz. Bu nedenle, toplu olarak, tüm ifadelerin zaman karmaşıklığı O(1) olarak kabul edilebilir. Şimdi bu ifadenin her biri Log(n) defa çalıştırılacaktır. Bu nedenle, zaman karmaşıklığı genellikle girdinin boyutuna bağlı olarak en yüksek karmaşıklık derecesi cinsinden ölçülür.
  • Ayrıca, aramaya çalıştığımız öğe orijinal dizinin orta dizinindeyken, öğeyi ilk yinelemenin kendisinde bulabileceğimiz durumlar olabilir, ancak bu, zaman karmaşıklığını tanımlamak için en iyi durumdur. Bir algoritmanın, her zaman en kötü durumu alır ve en kötü durum için algoritmanın Zaman karmaşıklığını belirtiriz.

PS Matematik kökenli olmayanlar için Log, üs almanın tam tersidir. Örneğin, bir sayıyı, diyelim ki 2’yi, kendisi ile birkaç kez çarpmaya devam edersek, n ​​deyin, şöyle bir ifade elde ederiz. 2n. Benzer şekilde, bir ifadeyi yine 2’ye bölmeye devam edersek, elde edilen değer şu şekilde hesaplanabilir: Günlük (n) böldüğümüz sayının tabanına (burada 2).

ile algoritmalar Logaritmik Zaman karmaşıklığı her adımda bir dizi girdiyi veya büyük bir miktarı ortadan kaldırdığımız için genellikle iyi programlardan biri olarak kabul edilir. Logaritmik Zaman karmaşıklığına sahip diğer algoritma örnekleri şunlardır:

  • Bir ondalık sayının İkili eşdeğerini bulma -> Günlük2(n)
  • Bir Sayının Rakamlarının Toplamını Bulma -> Log10(n)

Not bu algoritmalarda zaman karmaşıklığının “eleman sayısına” değil, “girdinin boyutuna” bağlı olduğunu.

Diğer Ortak Zaman Karmaşıklıkları

Doğrusal Zaman Karmaşıklığı

Hesaplama karmaşıklığının veya işlem sayısının girdi boyutu veya sayısındaki artışla doğrusal olarak arttığı herhangi bir algoritma, algoritmanın Zaman Karmaşıklığının Doğrusal olduğu söylenir ve ile gösterilir. Açık)

Zaman Karmaşıklığının Doğrusal olduğu bazı algoritma örnekleri:

  • Doğrusal Arama algoritması
  • Bir dizideki tüm öğelerin toplamını bulun
  • Bir sayının asal olup olmadığını bulmak için saf algoritma (kendisinden küçük her sayıya bölerek)

Linearitmik Zaman Karmaşıklığı

zaman karmaşıklığına sahip herhangi bir algoritma O(n günlük(n)) Linearitmik Zaman Karmaşıklığına sahip olduğu söylenir. Genellikle Merge Sort, Heap Sort, Tim Sort, Cube Sort gibi “Böl ve Yönet” özelliklerine sahip sıralama algoritmaları bu kategoriye girer.

Örneğin, Birleştirme Sıralaması diziyi her adımda ( O(log N)) ikiye bölmeye devam eder ve ardından her yarı için aynı birleştirme işlemini ( O(n) ) gerçekleştirir, dolayısıyla zaman karmaşıklığı O(n log n) olur.

İkinci Dereceden Zaman Karmaşıklığı

Girdinin her bir öğesi için, n işlem gerçekleştirmemiz gerekiyorsa, sonuçta ortaya çıkan zaman karmaşıklığının O(n) olacağı bir algoritma *veya Açık2) ve Kuadratik Zaman Karmaşıklığına sahip olduğu söylenir.

Örneğin, Kabarcık Sıralaması veya Seçimli Sıralama gibi basit sıralama tekniklerinin çoğunda, her bir öğeyi dizideki diğer tüm öğelerle karşılaştırmamız ve böylece n boyutundaki bir dizi için n X n işlemleri gerçekleştirmemiz gerekir.

Genel olarak, bu zaman karmaşıklığını şuna benzeyen iç içe geçmiş bir döngü ile tanımlayabilirsiniz.


for (int i = 0 ; i < n ; i++)
{
	for (int j = 1 ; j < n ; j++)
	{	
		Do something;
	}
}


NOT bazı algoritmaların birbiri ardına iki döngü yapısına sahip olabileceği ancak iç içe geçmediği. Gibi bir şey


for (int i = 0 ; i < n ; i++)
{
	for (int j = 1 ; j < n ; j++)
	{	
		Do something;
	}
}

for (int i = 0 ; i < n ; i++)
{
	Do something;
}

for (int i = 0 ; i < n ; i++)
{
	Do something;
}


Burada Zaman Karmaşıklığı O(n) olacaktır.2) + O(n) + O(n) = O(n)2) + O(2n) . Daha önce de belirtildiği gibi, zaman karmaşıklığını dikkate alırken her zaman en yüksek dereceli işlevi dikkate alacağız ve bu nedenle bu tür algoritmaların Zaman karmaşıklığı O(n) olarak kabul edilecektir.2) sadece.

Kübik Zaman Karmaşıklığı

Tahmin etmek için şeker yok! Zaman karmaşıklığına sahip algoritmalar Açık3) Kübik Zaman Karmaşıklığına sahip olduğu söyleniyor

Aşağıdaki gibi ikinci dereceden bir denklemde x, y ve z’nin değerini bulmanın bir örneğini düşünün.

3x + 2y + z = 45

Programlı olarak, tüm x, y ve z kombinasyonlarında 3x + 2y + z’nin 45 olduğu bir durumu bulmak için üç iç içe döngüden geçmeniz gerekecek, aşağıdaki gibi bir şey


for  (int x = 0 ; x < n ; x++)
{
	for  (int y = 0 ; y < n ; y++)
	{
		for  (int z = 0 ; z < n ; z++)
		{
			if(3*x + 2*y + z == n)
			{
				print(x, y, z);
				Return;
			}
		}
	}
}


Kübik zaman karmaşıklığına sahip başka bir algoritma örneği, Matris Çarpımıdır.

Gibi çeşitli zaman karmaşıklığına sahip başka birçok algoritma türü vardır. Üstel, Polinom, Faktöriyel ve biraz araştırma yapmak ve hakkında daha fazla çalışmak için okuyucuya bırakacağım diğerleri.

İşte çeşitli zaman karmaşıklıklarını ve artan girdi ile nasıl arttığını gösteren bir grafik

Algoritmaların Karmaşıklığı

Bir cevap yazın

Ready to Grow Your Business?

We Serve our Clients’ Best Interests with the Best Marketing Solutions. Find out More

How Can We Help You?

Need to bounce off ideas for an upcoming project or digital campaign? Looking to transform your business with the implementation of full potential digital marketing?

For any career inquiries, please visit our careers page here.
[contact-form-7 404 "Bulunamadı"]