Gereksinimler: Koleksiyonu eklemeyen, silmeyen veya değiştirmeyecek, sadece koleksiyonu sorgulayan tek okuma amaçlı bir koleksiyon türü tanımlamanız gerekir. UmarızSorgu ne kadar hızlı olursa, o kadar iyi。
Yaygın küme karşılaştırmaları
Algoritmanın karmaşıklığını tanımlarken, o(1), o(n), o(logn), o(logn), o(logn), o(nlogn) genellikle ilgili algoritmanın zaman karmaşıklığını ifade etmek için kullanılır; bu algoritma algoritmanın uzaylı-zamansal karmaşıklığının ifadesidir. Sadece zamansal karmaşıklığı temsil etmek için değil, aynı zamanda mekânsal karmaşıklığı da temsil etmek için kullanılır.
O ardından, bir algoritmanın tükettiği zaman/uzay ile yetiştirilen veri miktarı arasındaki ilişkiyi gösteren parantez içindeki bir fonksiyon gelir. burada n giriş veri miktarını temsil eder.
Örneğin, zaman karmaşıklığı O(n) ise, veri miktarının birkaç kat arttığı ve zaman tüketiminin de birkaç kat arttığı anlamına gelir. Örneğin, yaygın geçiş algoritmaları. Bir diğer örnek ise zaman karmaşıklığı O(n^2)'dir; bu, veri hacmi n kat arttığında, n kare kat artması zaman alır ve bu da doğrusal zaman karmaşıklığından daha yüksek bir zaman karmaşıklığıdır. Örneğin, balon sıralaması tipik bir O(n^2) algoritmasıdır ve n sayıyı sıralamak için n × n kez taranması gerekir.
Bir diğer örnek O(logn)'dur; veri n kat arttığında, logn sürelerini artırmak zaman alır (burada log 2'ye dayanır, örneğin veri 256 kat artırıldığında, gereken süre sadece 8 kat artar, bu da doğrusal zamandan daha azdır). İkili arama, O (logn) algoritmasıdır; her bulunduğunda olasılıkların yarısını ortadan kaldırır ve 256 verideki arama hedefi bulmak için sadece 8 kez bulunması yeterlidir.
O(nlogn) aynıdır, yani n logn ile çarpılır; veri 256 kat artırıldığında zaman tüketimi 256 * 8 = 2048 kat artar. Bu karmaşıklık, karenin altındaki doğrusal çizgiden daha yüksektir. Birleştirme ve sıralama, O(nlogn)'un zaman karmaşıklığıdır.
O(1) en düşük uzaylı-zaman karmaşıklığıdır; yani, tüketilen zaman/uzay girdi verinin boyutundan bağımsızdır; giriş verisi kaç kez artırılırsa artsın, tüketilen zaman/uzay değişmez. Hashing algoritması, tipik bir O(1) zaman karmaşıklığıdır ve veri ne kadar büyük olursa olsun tek bir hesaplamadan sonra (çatışmalara rağmen) hedefi bulabilir.
Bu makale BenchmarkDotNet çiftini kullanırList、HashSet、SortedSet、DictionaryKıyaslama için sorgu, aşağıdaki bölümlere bakınız:
Kod şöyledir:
Test sonucu: Bir Sözlükte veya HashSet'te bir anahtar bulmak, List ve SortedSet'te arama yapmaktan çok daha hızlıdır. Sözlük ve HashSet algoritmalarının zaman karmaşıklığı O(1)'dir ve hafıza tasarrufu için Sözlüğün Değeri bize faydası yok, bu yüzden yine de HashSet depolamayı seçtim.
|
Yayınlandı 7.03.2022 16:47:50
|
|
|
|
Yayınlandı 7.03.2022 23:09:48
|
Ev sahibi|
Yayınlandı 9.03.2022 09:55:12
|
