10^8 Pratik Kuralı

Tipik bir çevrim içi değerlendirici saniyede yaklaşık 10^8 basit işlem yürütür. Bu sayı, tüm program için harcayabileceğiniz bütçedir. 💡

İşlem sayınızı adım başına iş miktarıyla çarpın, ardından sonucu zaman sınırıyla karşılaştırın. Adımlar bütçeye sığıyorsa büyük olasılıkla başarılı olursunuz.

n = 10^6 için yapılan bir O(n) taraması yalnızca bir milyon adımdır ve bütçenin oldukça altındadır. Doğrusal çözümler neredeyse her zaman rahatça başarılı olur.

n = 10^6 için O(n log n) bir sıralama yaklaşık 2 çarpı 10^7 adım sürer. Bu hâlâ bir saniyelik bütçenin oldukça içindedir; dolayısıyla sıralama nadiren darboğaz olur.

O(n^2) yaklaşımı, 10^8 adıma mal olduğu n = 10^4 civarında bütçeye ulaşır. Bu noktadan sonra karesel çözümler zaman aşımına uğramaya başlar.

O(n^3) çözümü yalnızca yaklaşık n = 500'e kadar dayanır. n'nin küpünü aldığınızda yaklaşık 10^8 adıma, yani bütçenin sınırına ulaşırsınız.

O(2^n) her adımda iki katına çıkar; bu nedenle yalnızca 20 ile 25 arasındaki çok küçük n değerleri için çalışır. Bundan sonra işlem sayısı 10^8'i aşarak patlar.

Python her adımda daha yavaştır; bu nedenle sıkı döngülerde bütçeyi 10^7'ye daha yakın kabul edin. Kısıtlar sınırdaysa temkinli davranın.

10^8 kuralı basit adımları sayar. Döngü içindeki metin oluşturma gibi ağır işler, gerçek bütçenizi azaltan bir sabit çarpan ekler.

Zaman sınırı genellikle 1 veya 2 saniyedir. 2 saniyelik bir sınır bütçenizi yaklaşık olarak iki katına çıkarır ve size biraz daha hareket alanı sağlar.

Önce her zaman n'yi karmaşıklık ifadenizde yerine koyup 10^8 ile karşılaştırın. Bu hızlı tutarlılık kontrolü, sizi başarısız olması kaçınılmaz bir çözümü kodlamaktan kurtarır.

10^8 kuralını uygulayın.

Artık işlemleri zamana dönüştürebiliyorsunuz: saniyede yaklaşık 10^8 işlem. Doğrusal ve n log n çözümler güvenlidir, karesel çözümler n = 10^4 civarında sınıra ulaşır; siz de kodlamadan önce kontrol edersiniz. ✅