Karmaşıklık teorisi hakkında bilmeniz gerekenler
Karmaşıklık teorisi, teorik bilgisayar biliminin algoritmaların tasarımını ve analizini etkileyen bir tema alanıdır. Ancak, konunun uygulama için de ilgisi vardır. Bu konuda ne bilmelisin?
Karmaşıklık teorisinin başlangıç noktası, çözümünü bir soruna çözmek için bir algoritma bulma veya tasarlama görevidir. Böyle bir algoritma, mümkünse, yani farklı kriterleri karşılamak için “iyi” olmalıdır. Bu, doğruluk ve güvenilirliği, aynı zamanda yüksek bir hız ve küçük bir depolama gereksinimini de içerir.
Bununla birlikte, çok fazla bellek tüketen hızlı bir algoritma ile bellekle ilgilenen bir yavaş algoritma arasında seçime sahip olmak için belleğin hızı ve gereksinimi genellikle önde davranır. En basit durumda, bir algoritma hesaplanan ara sonuçların önbelleği ile hızlandırılabilir, bu nedenle bellek gereksinimini arttırır.
Önemli bir soru, bir algoritmanın hızını vermek gibidir. Genellikle mutlak bir zaman belirlemek hassas değildir, çünkü bir yandan CPU gerçekten kullanılan CPU'ya bağlıdır, aynı zamanda APUT'un boyutlarına da bağlıdır: Tabii ki, 100 element listesinden karşılaştırıldığında 1000 element listesinden maksimumu belirlemek daha fazla zaman alır.
Bu nedenle, karmaşıklık teorisinin temel fikri, APUT'un boyutuna bağlı bir fonksiyon için bir algoritmanın terimini tanımlamaktır. Bununla birlikte, bunlar işlev tarafından belirlenen somut değerler değil, doğrusal, kare, kübik veya başka bir fonksiyon olsun, türlerine göre.
Bu açıklamayı belirtmek için, doğrusal bir çaba gösteren bir algoritmaya sahip SO -CALLED O. gösterimi vardır, “O
” den, “O (n^2)” ve benzeri kare bir çaba ile bahsediyoruz.Önerilen editoryal içerik
Rızanızla, burada harici bir YouTube videosu (Google Ireland Limited) burada davet edilir.
YouTube videosu her zaman yüklenir
YouTube videosu artık yüklüyor
Karmaşıklık teorisi nedir?
Polinom karmaşıklığı
Bir listenin maksimum değerini belirleme çabası doğrusaldır: listenin her bir öğesi en az bir kez bulunan maksimum ile karşılaştırılmalıdır, doğrusal algoritmanın çabası eleman sayısı ile artar. Öte yandan, bir sayı listesinden tüm olası çiftleri oluşturma çabası kare'dir, çünkü her element başka bir öğeyle birleştirilmelidir.
Tüm faktörler ihmal edilir. Dolayısıyla, bir algoritmanın bir veya iki kez bir listeden geçmesi önemli değil, çaba her iki durumda da doğrusaldır. Bunun nedeni, özellikle büyük girdiler için potansiyel bir faktörün, kare nedeniyle olası güçlere kıyasla önemli olmamasıdır (“x^2” “2x” veya “10x” dan daha hızlı artmaktadır).
Özel bir durum “O (1)” i temsil eder, bu da sürekli bir çaba içindir: bu durumda, algoritmanın APUT'un boyutuna bakılmaksızın her zaman aynı uzunluğa ihtiyacı vardır. Bu, örneğin, bir dizinin öğelerine erişirken, istenen öğe adresi doğrudan hesaplanabilir ve bu nedenle listenin uzunluğundan bağımsızdır.
Şimdiye kadar bahsedilen tüm işlevlerin bir polinom tarafından tanımlanabilecek ortak yönleri vardır. Polynomy'nin tanımlanabileceği algoritmalar genellikle “iyi” olarak kabul edilir, çünkü şüphe varsa, daha hızlı bir CPU tarafından açıkça hızlandırılabilirler, bu yüzden daha yüksek boyut mümkündür.
Örneğin, yüz kat daha hızlı CPU olan doğrusal karmaşıklık ile, kare karmaşıklık, hala düzinelerce problemle yüz kat daha büyük çözmenizi sağlar. Bu nedenle polinom terimi ile çalışan algoritmalar daha fazla veya daha iyi donanım ile önemli ölçüde geliştirilebilir.
Önerilen editoryal içerik
Rızanızla, burada harici bir YouTube videosu (Google Ireland Limited) burada davet edilir.
YouTube videosu her zaman yüklenir
YouTube videosu artık yüklüyor
Polinom karmaşıklığı
Popüler olmayan karmaşıklık
Bununla birlikte, bu, terimi polinom değil, örneğin katlanarak olan algoritmalar için geçerli değildir. Şimdiye kadar polinom terimi ile algoritmanın bulunamaması sorun “seyahat satışları” (TSP) sorunudur. Görevi birkaç şehri gezmek ve mümkün olduğunca kısa bir yol seçmek olan bir satış temsilcisi ile ilgilidir.
Olası her yolu belirlemek ve bu nedenle ondan en kısa olanı seçmek için saf çözüm tüm kenarları hızla kırar. Birinci şehir “n” için, ikinci “N-1” için, üçüncü “N-2” için ve benzeri için olasılıklar olduğundan, olası yolların sayısı, fakülte çok hızlı bir şekilde artar. Bu nedenle bu prosedürü seçen bir algoritmanın fakülte tarafından tanımlanan bir terimi vardır. Polinom çabası olan TSP için bir çözüm olup olmadığı bilinmemektedir.
Bu algoritmalarla ilgili sorun, önemli ölçüde daha güçlü CPU nedeniyle, problemlerin veya (önceki) çözümlerinin çok karmaşık olduğu için sorunun büyüklüğünde önemli bir artış mümkün değildir.
Önerilen editoryal içerik
Rızanızla, burada harici bir YouTube videosu (Google Ireland Limited) burada davet edilir.
YouTube videosu her zaman yüklenir
YouTube videosu artık yüklüyor
Polinom karmaşıklığı
Karmaşıklık sınıfları olarak P, NP & Co.
Tüm sorunlar farklı karmaşıklık sınıflarında sınıflandırılabilir. En basit sınıf “P” dir ve polinom terimine sahip bir algoritmanın olduğu tüm sorunları içerir. Adından farklı olarak, “NP” sınıfı, polinom olmayan sürede çözülebilecek sorunları içermez, ancak toplanan bir çözümün polinom zamanlarında kontrol edilebileceği problemler içerir. “NP” bu nedenle “” belirsiz olmayan polinomu “temsil eder.
Tüm NP problemleri eşit derecede zor değildir. Birlikte “NP-Schwer” sınıfını oluşturan özellikle zor ve hatta çözülemez olanlar vardır. NP ve NP-SHW kısmen örtüşüyor. Bu kavşak da “Fuzione NP” olarak gösterilmiştir. NP-Fucen'in özel olan, tüm NP problemlerinin matematiksel olarak herhangi bir NP-Full problemine atfedilebilmesidir.
Bu, bir polinom teriminde tek bir NP tamamlama problemini çözmeyi başarırsa, polinom zamanındaki tüm NP problemlerinin otomatik olarak çözüleceği anlamına gelir. P ve NP sınıfı bu durumda aynı olacaktır. Açık olup olmadığı.
Önerilen editoryal içerik
Rızanızla, burada harici bir YouTube videosu (Google Ireland Limited) burada davet edilir.
YouTube videosu her zaman yüklenir
YouTube videosu artık yüklüyor
Karmaşıklık sınıfları olarak P, NP & Co.
NP-Folication nedir?
Bu anlamda, NP için spesifik problemler NP'nin kaynağıdır. NP için zaten belirli bir problem örneği verilmiştir, yani TSP. Başka bir NP tamamlama problemi, paketlenmiş nesnelerin değerini optimize eden, ancak bir dizi nesnenin paketlenmesinin mümkün olmadığı gerçeğini dikkate alarak, bir dizi nesnenin ambalajlanmasıyla ilgili sırt çantasının sorunudur.
Bazı durumlarda, büyük ama değerli bir nesne seçilmemesi tavsiye edilir, çünkü iki küçük olanın kombinasyonu toplamda daha değerlidir ve sırt çantasında daha az yer alır. Bu TSP'de zaten belirgindir: burada da, bir yolun çok kısa bir bölümünü atlamak ve daha uzun bir yolu kabul etmek de mantıklı olabilir. Bu, kısa bölüm başka bir yerde gereksiz yere uzun bir sapmaya yol açarsa geçerlidir.
Polinom zamanlarında NP'nin spesifik sorunlarından birini çözmeyi başarırsa, P ve NP aynı olacaktır. Ancak, P ve NP aynı değilse, NP ve NP-Fucht aynı değildir. Bu nedenle NP tüm “orta” sorunları içerir.
P ve NP'nin aynı olup olmadığı gösterilmemesi (veya çürütülmemesinin) dışında, P ve NP arasındaki ilişkinin hiç gösterilebileceği bile gösterilmemiştir. Bu, konuyu özellikle heyecan verici ve uyarıcı hale getirir.
Önerilen editoryal içerik
Rızanızla, burada harici bir YouTube videosu (Google Ireland Limited) burada davet edilir.
YouTube videosu her zaman yüklenir
YouTube videosu artık yüklüyor
NP-Folication nedir?
Çözüm
Konu esas olarak pratiktir, çünkü belirli bir sorun için “iyi” bir çözüm olmayabileceğini gösterebilirsiniz, bu nedenle asla bulamayacağınız için bir çözüm aramaya devam etmek işe yaramaz.
()