project euler 7.soru

quote:

Orijinalden alıntı: ecivas

Asal Sayı Test Fonskiyonunuzu Aşağıdaki Mantıkla Çalışır Hale Getirirseniz, Uygulamanızın Hızlandığını Göreceksiniz.
Kendim Test Ettim (İşlem Süreleri Aşağıda)

10001. Asal Sayı = 1.81 saniye
20000. Asal Sayı = 7.54 saniye
30000. Asal Sayı = 18.79 saniye
40000. Asal Sayı = 36.21 saniye
50000. Asal Sayı = 57.83 saniye

 
  /** 
       * Asal Sayı Testi 
       * 1 Asal Sayı Değildir, 
       * Bir Sayının Asal Sayı Olabilmesi İçin, 1 ve Kendisi Dışındaki 
       * Sayıların Hiçbirinin O Sayıyı Kalansız Bölmemesi Gerekir. 
       * Eğer 1 - n Arasındaki Sayılardan Bir Tanesi Bile Sayıyı Kalansız 
       * Bölüyorsa, Sayı Asal Değildir. Dolayısıyla Test İşlemine Devam Etmeye Gerek Yoktur 
       *  
       * @param n Test Edilecek Sayı 
       * @return Sayı Asalsa True, Sayı Asal Değilse False Döner 
       */ 
      public static boolean isPrime(int n) 
      { 
          if (n == 1) return false; 
          for (int i = 2; i<n; i++) 
              if (n % i == 0) return false; 
          return true; 
      } 
  

Şu an için değil, ama ileride kendinizi geliştirdiğinizde, lütfen aynı uygulamayı farklı threadler kullanarak yapmayı deneyin.
örneğin eş zamanlı olarak 2-3 thread çalıştırıp iş yükünü bölün, harcanan sürenin %30 gibi bir oranda azaldığını göreceksiniz :)

Yazmış olduğunuz kodtaki sıkıntı
Siz hangi sayı olursa olsun, tüm sayıları kalansız bölüyor mu diye kontrol ediyorsunuz, halbuki 1 - n arasındaki herhangi bir sayı n'i kalansız olarak bölüyorsa, o an evet bu asal değil diye işleme devam etmelisiniz,
bunun yerine siz, en sona kadar gidiyorsunuz.

örneğin :
3 - 10 arasındaki sayıların testini yapacak olursak
(sizin programın mantığı)
3 -> 3 kere döner
4 -> 4 kere döner
5 -> 5 kere döner
6 -> 6 kere döner
7 -> 7 kere döner
8 -> 8 kere döner
9 -> 9 kere döner
10 -> 10 kere döner

toplam = 52 kez aynı işlem tekrar edilir.

(benim verdiğim örnekteki mantık)
3 -> 1 kere döner
4 -> 1 kere döner
5 -> 3 kere döner
6 -> 1 kere döner
7 -> 5 kere döner
8 -> 1 kere döner
9 -> 2 kere döner
10 -> 1 kere döner
toplam = 14 kez aynı işlem tekrar edilir.

eğer sayıları büyütecek olursak farkı anlarsınız

10000 - 10005 arasındaki sayıların testi :

(sizin programın mantığı)
10000 -> 10000 kere döner
10001 -> 10001 kere döner
10002 -> 10002 kere döner
10003 -> 10003 kere döner
10004 -> 10004 kere döner
10005 -> 10005 kere döner

toplam = 60015 kere aynı işlem tekrar edilir

(benim verdiğim örnekteki mantık)
10000 -> 1 kere döner
10001 -> 73 kere döner
10002 -> 1 kere döner
10003 -> 6 kere döner
10004 -> 1 döner
10005 -> 2 kere döner
toplam = 84 kere aynı işlem tekrar edilir.

umarım örnekler açıklayıcı olmuştur.

quote:

Orijinalden alıntı: ThisisaNightmare

quote: Orijinalden alıntı: ecivas Asal Sayı Test Fonskiyonunuzu Aşağıdaki Mantıkla Çalışır Hale Getirirseniz, Uygulamanızın Hızlandığını Göreceksiniz. Kendim Test Ettim (İşlem Süreleri Aşağıda) 10001. Asal Sayı = 1.81 saniye 20000. Asal Sayı = 7.54 saniye 30000. Asal Sayı = 18.79 saniye 40000. Asal Sayı = 36.21 saniye 50000. Asal Sayı = 57.83 saniye /** * Asal Sayı Testi * 1 Asal Sayı Değildir, * Bir Sayının Asal Sayı Olabilmesi İçin, 1 ve Kendisi Dışındaki * Sayıların Hiçbirinin O Sayıyı Kalansız Bölmemesi Gerekir. * Eğer 1 - n Arasındaki Sayılardan Bir Tanesi Bile Sayıyı Kalansız * Bölüyorsa, Sayı Asal Değildir. Dolayısıyla Test İşlemine Devam Etmeye Gerek Yoktur * * @param n Test Edilecek Sayı * @return Sayı Asalsa True, Sayı Asal Değilse False Döner */ public static boolean isPrime(int n) { if (n == 1) return false; for (int i = 2; i<n; i++) if (n % i == 0) return false; return true; } Şu an için değil, ama ileride kendinizi geliştirdiğinizde, lütfen aynı uygulamayı farklı threadler kullanarak yapmayı deneyin. örneğin eş zamanlı olarak 2-3 thread çalıştırıp iş yükünü bölün, harcanan sürenin %30 gibi bir oranda azaldığını göreceksiniz :) Yazmış olduğunuz kodtaki sıkıntı Siz hangi sayı olursa olsun, tüm sayıları kalansız bölüyor mu diye kontrol ediyorsunuz, halbuki 1 - n arasındaki herhangi bir sayı n'i kalansız olarak bölüyorsa, o an evet bu asal değil diye işleme devam etmelisiniz, bunun yerine siz, en sona kadar gidiyorsunuz. örneğin : 3 - 10 arasındaki sayıların testini yapacak olursak (sizin programın mantığı) 3 -> 3 kere döner 4 -> 4 kere döner 5 -> 5 kere döner 6 -> 6 kere döner 7 -> 7 kere döner 8 -> 8 kere döner 9 -> 9 kere döner 10 -> 10 kere döner toplam = 52 kez aynı işlem tekrar edilir. (benim verdiğim örnekteki mantık) 3 -> 1 kere döner 4 -> 1 kere döner 5 -> 3 kere döner 6 -> 1 kere döner 7 -> 5 kere döner 8 -> 1 kere döner 9 -> 2 kere döner 10 -> 1 kere döner toplam = 14 kez aynı işlem tekrar edilir. eğer sayıları büyütecek olursak farkı anlarsınız 10000 - 10005 arasındaki sayıların testi : (sizin programın mantığı) 10000 -> 10000 kere döner 10001 -> 10001 kere döner 10002 -> 10002 kere döner 10003 -> 10003 kere döner 10004 -> 10004 kere döner 10005 -> 10005 kere döner toplam = 60015 kere aynı işlem tekrar edilir (benim verdiğim örnekteki mantık) 10000 -> 1 kere döner 10001 -> 73 kere döner 10002 -> 1 kere döner 10003 -> 6 kere döner 10004 -> 1 döner 10005 -> 2 kere döner toplam = 84 kere aynı işlem tekrar edilir. umarım örnekler açıklayıcı olmuştur.

Daha iyi algoritmalar da var:

http://en.wikibooks.org/wiki/Efficient_Prime_Number_Generating_Algorithms

Burada bakicak olursak en son verilen algoritma 10000. ci sayiyi 0.01 saniyede veriyor. Ilk algoritma bile 10000. ci sayiyi 1.6 saniyede veriyor.

Yapilmasi basit ve anlasilir olan 3. algoritma. Tabi bunu anlamak icin ilk 2 algoritmayi anlamak gerekiyor.

1. algoritma:
Sayi asal mi degil mi bunu ogrenmek icin elimizde bir liste olur ve bu listede sadece karsilastigimiz asal sayilar bulunur, mevcut sayi bu listedeki sayilara bolunmuyorsa mevcut sayi bu listeye eklenir. Mevcut listeye 2 sayisini ekleyerek basliyoruz ve 3 ten itibaren baslayarak bu algoritmayi uyguluyoruz. (100 000 inci sayiya 130 saniyede ulasiyor bu algoritma)

2. algoritma:
2 den baska hic bir cift sayi asal degildir. O zaman neden 2 ile ugrasiyoruz ki? 3 ten baslayip sayiyi cifter cifter arttirirsak hep tek sayilara bakmis oluruz. (100 000 inci sayiya 65 saniyede ulasiyor)

3. algoritma:
Baktigimiz sayinin karekoku eger listedeki bolmeyi kontrol ettigimiz sayidan buyukse o zaman listeye bakmaya devam etmeye gerek yoktur, cunku karekokunden buyuk sayilar asal sayinin kendi bolumu olamaz. (100 000 inci sayiya 27 saniyede ulasiyor)

Alıntıları Göster

quote:

Orijinalden alıntı: welrocken

Yukarıda verilen sitedeki algoritma n. asal sayıyı değil, n'e kadar olan asal sayıları veriyordu dolayısıyla biraz bi değişiklik yaptım, 10000. asal sayıyı (değişiyor sürekli ama) 300-350 ms'de falan buluyorum, kullandığım kod şu (birebir geçirmeye çalıştım, C#);

static List<long> allPrimes(long n) 
          { 
              long pp = 2; 
              int sqrtPP; 
              bool test; 
              List<long> allPrime = new List<long>(); 
              pp++; 
              allPrime.Add(pp); 
              while (pp < n) 
              { 
                  pp += 2; 
                  test = true; 
                  sqrtPP = (int)Math.Sqrt(pp); 
                  for (int i = 0; i < allPrime.Count; i++) 
                  { 
   
                      if (allPrime[i] > sqrtPP) 
                          break; 
                      if (pp % allPrime[i] == 0) 
                      { 
                          test = false; 
                          break; 
                      } 
                      if (test) 
                      { 
                          allPrime.Add(pp); 
                      } 
                  } 
              } 
              return allPrime; 
          }

Benzer bir mantıkla çalışan kendi kodum ise 350-450 ms arasında sonuç veriyor;

static long ninciAsal(int n) 
          { 
              List<long> asallar = new List<long>(); 
              long l = 2; 
              long lastAsal = 0; 
              int i = 0; 
              while (i < n) 
              { 
                  while (!asal(l, asallar)) 
                  { 
                      l++; 
                  } 
                  asallar.Add(l); 
                  lastAsal = l; 
                  l++; 
                  i++; 
              } 
              return lastAsal; 
          } 
   
          static bool asal(long sayi, List<long> asallar) 
          { 
              if (sayi > 1) 
              { 
                  bool asal = true; 
                  int maxi = 0; 
                  long sayiKok = (long)Math.Sqrt(sayi); 
                  foreach (long l in asallar) 
                  { 
                      if (l <= sayiKok) 
                      { 
                          maxi++; 
                      } 
                      else 
                      { 
                          break; 
                      } 
                  } 
                  for (int i = 0; i < maxi; i++) 
                  { 
                      if (sayi % asallar[i] == 0) 
                      { 
                          asal = false; 
                          break; 
                      } 
                  } 
                  return asal; 
              } 
              else 
              { 
                  return false; 
              } 
          }

Bu 100 ms'lik fark nereden kaynaklanıyor olabilir? Kodumda değişiklik yapılması gereken yerler mi var acaba?

Kullanım;

 
              Stopwatch sw = Stopwatch.StartNew(); 
              long l = ninciAsal(10000);//kendi fonksiyonum 
              sw.Stop(); 
              Console.WriteLine(ninciAsal(10000)); 
              Console.WriteLine("Found in : " + sw.ElapsedMilliseconds.ToString()); 
              sw.Restart(); 
              List<long> allprms = allPrimes(l);//sitedeki algoritmanın C#'a dönüştürülmüş hali (olduğu kadar) 
              sw.Stop(); 
              Console.WriteLine(allprms[allprms.Count - 1]); 
              Console.WriteLine("Found in: " + sw.ElapsedMilliseconds); 
  

quote:

Orijinalden alıntı: ThisisaNightmare

quote: Orijinalden alıntı: welrocken Yukarıda verilen sitedeki algoritma n. asal sayıyı değil, n'e kadar olan asal sayıları veriyordu dolayısıyla biraz bi değişiklik yaptım, 10000. asal sayıyı (değişiyor sürekli ama) 300-350 ms'de falan buluyorum, kullandığım kod şu (birebir geçirmeye çalıştım, C#); static List<long> allPrimes(long n) { long pp = 2; int sqrtPP; bool test; List<long> allPrime = new List<long>(); pp++; allPrime.Add(pp); while (pp < n) { pp += 2; test = true; sqrtPP = (int)Math.Sqrt(pp); for (int i = 0; i < allPrime.Count; i++) { if (allPrime[i] > sqrtPP) break; if (pp % allPrime[i] == 0) { test = false; break; } if (test) { allPrime.Add(pp); } } } return allPrime; } Benzer bir mantıkla çalışan kendi kodum ise 350-450 ms arasında sonuç veriyor; static long ninciAsal(int n) { List<long> asallar = new List<long>(); long l = 2; long lastAsal = 0; int i = 0; while (i < n) { while (!asal(l, asallar)) { l++; } asallar.Add(l); lastAsal = l; l++; i++; } return lastAsal; } static bool asal(long sayi, List<long> asallar) { if (sayi > 1) { bool asal = true; int maxi = 0; long sayiKok = (long)Math.Sqrt(sayi); foreach (long l in asallar) { if (l <= sayiKok) { maxi++; } else { break; } } for (int i = 0; i < maxi; i++) { if (sayi % asallar[i] == 0) { asal = false; break; } } return asal; } else { return false; } } Bu 100 ms'lik fark nereden kaynaklanıyor olabilir? Kodumda değişiklik yapılması gereken yerler mi var acaba? Kullanım; Stopwatch sw = Stopwatch.StartNew(); long l = ninciAsal(10000);//kendi fonksiyonum sw.Stop(); Console.WriteLine(ninciAsal(10000)); Console.WriteLine("Found in : " + sw.ElapsedMilliseconds.ToString()); sw.Restart(); List<long> allprms = allPrimes(l);//sitedeki algoritmanın C#'a dönüştürülmüş hali (olduğu kadar) sw.Stop(); Console.WriteLine(allprms[allprms.Count - 1]); Console.WriteLine("Found in: " + sw.ElapsedMilliseconds);

While loopunda sadece 1 ekliyorsun 2 eklemek yerine. asallar.Add(2) deyip l i 3 ten baslatirsan while dongusunun icindede l i 2 ser 2 ser arttirirsan algoritma hizlanir gibi duruyor.
2. olarak ise asal methodunda foreach loop ile for loopun var. For loop gereksiz duruyor. Foreach loopunda yapmak istedigini direkt yapmalisin gerek yok maxi yapip saymaya. Yapicagini orada yap (sayi buyuk mu check et, daha sonra bolunuyor mu onu check et)

quote:

Orijinalden alıntı: welrocken

quote: Orijinalden alıntı: ThisisaNightmare quote: Orijinalden alıntı: welrocken Yukarıda verilen sitedeki algoritma n. asal sayıyı değil, n'e kadar olan asal sayıları veriyordu dolayısıyla biraz bi değişiklik yaptım, 10000. asal sayıyı (değişiyor sürekli ama) 300-350 ms'de falan buluyorum, kullandığım kod şu (birebir geçirmeye çalıştım, C#); static List<long> allPrimes(long n) { long pp = 2; int sqrtPP; bool test; List<long> allPrime = new List<long>(); pp++; allPrime.Add(pp); while (pp < n) { pp += 2; test = true; sqrtPP = (int)Math.Sqrt(pp); for (int i = 0; i < allPrime.Count; i++) { if (allPrime[i] > sqrtPP) break; if (pp % allPrime[i] == 0) { test = false; break; } if (test) { allPrime.Add(pp); } } } return allPrime; } Benzer bir mantıkla çalışan kendi kodum ise 350-450 ms arasında sonuç veriyor; static long ninciAsal(int n) { List<long> asallar = new List<long>(); long l = 2; long lastAsal = 0; int i = 0; while (i < n) { while (!asal(l, asallar)) { l++; } asallar.Add(l); lastAsal = l; l++; i++; } return lastAsal; } static bool asal(long sayi, List<long> asallar) { if (sayi > 1) { bool asal = true; int maxi = 0; long sayiKok = (long)Math.Sqrt(sayi); foreach (long l in asallar) { if (l <= sayiKok) { maxi++; } else { break; } } for (int i = 0; i < maxi; i++) { if (sayi % asallar[i] == 0) { asal = false; break; } } return asal; } else { return false; } } Bu 100 ms'lik fark nereden kaynaklanıyor olabilir? Kodumda değişiklik yapılması gereken yerler mi var acaba? Kullanım; Stopwatch sw = Stopwatch.StartNew(); long l = ninciAsal(10000);//kendi fonksiyonum sw.Stop(); Console.WriteLine(ninciAsal(10000)); Console.WriteLine("Found in : " + sw.ElapsedMilliseconds.ToString()); sw.Restart(); List<long> allprms = allPrimes(l);//sitedeki algoritmanın C#'a dönüştürülmüş hali (olduğu kadar) sw.Stop(); Console.WriteLine(allprms[allprms.Count - 1]); Console.WriteLine("Found in: " + sw.ElapsedMilliseconds); While loopunda sadece 1 ekliyorsun 2 eklemek yerine. asallar.Add(2) deyip l i 3 ten baslatirsan while dongusunun icindede l i 2 ser 2 ser arttirirsan algoritma hizlanir gibi duruyor. 2. olarak ise asal methodunda foreach loop ile for loopun var. For loop gereksiz duruyor. Foreach loopunda yapmak istedigini direkt yapmalisin gerek yok maxi yapip saymaya. Yapicagini orada yap (sayi buyuk mu check et, daha sonra bolunuyor mu onu check et)

Teşekkür ederim, deniyim, bir de okulda bir derste (Discreate Math di galiba) bir algoritmanın çalışma süresi ile ilgili birşey öğrenmiştik. Döngüler, tekrar edilen şeyler polinom olarak yazıp (iki iç içe döngü sanırım n^2 olarak yazılıyordu [ikisi de n kere dönüyorsa]), matematiksel işlemleri vs. constant olarak varsayıp işlem yapıyorduk (ve hesaba katmıyorduk, ama buradaki süre ölçerler herşeyi hesaba katıyor dolaylı olarak). Demek istediğim, bu süreler sadece bir deney sonucu, mesela benim kodum diğer algoritmadan çoğu denememde yaklaşık 100-150 ms uzun sürüyor ama belki de matematiğini yapsam, n sayısı çok büyüdüğünde 2 katı 10 katı vs. uzun sürecek. Dolayısıyla bu sürelere güvenmeli mi, yoksa oturup matematiksel hesabını mı yapmalı?

Sitedeki algoritmaların mantığı çok anlaşılır da burada paylaşılan o efsane kodu çözemedim, adresleme bilgimden kaynaklanıyor olabilir * ve & gördüğüm yerde bi korku basıyor, açıklaması var mıdır bi yerde?

Edit: efsane kod şu konudaymış kafa gitmiş;
http://forum.donanimhaber.com/m_98945826/tm.htm

quote:

Orijinalden alıntı: ThisisaNightmare

quote: Orijinalden alıntı: welrocken quote: Orijinalden alıntı: ThisisaNightmare quote: Orijinalden alıntı: welrocken Yukarıda verilen sitedeki algoritma n. asal sayıyı değil, n'e kadar olan asal sayıları veriyordu dolayısıyla biraz bi değişiklik yaptım, 10000. asal sayıyı (değişiyor sürekli ama) 300-350 ms'de falan buluyorum, kullandığım kod şu (birebir geçirmeye çalıştım, C#); static List<long> allPrimes(long n) { long pp = 2; int sqrtPP; bool test; List<long> allPrime = new List<long>(); pp++; allPrime.Add(pp); while (pp < n) { pp += 2; test = true; sqrtPP = (int)Math.Sqrt(pp); for (int i = 0; i < allPrime.Count; i++) { if (allPrime[i] > sqrtPP) break; if (pp % allPrime[i] == 0) { test = false; break; } if (test) { allPrime.Add(pp); } } } return allPrime; } Benzer bir mantıkla çalışan kendi kodum ise 350-450 ms arasında sonuç veriyor; static long ninciAsal(int n) { List<long> asallar = new List<long>(); long l = 2; long lastAsal = 0; int i = 0; while (i < n) { while (!asal(l, asallar)) { l++; } asallar.Add(l); lastAsal = l; l++; i++; } return lastAsal; } static bool asal(long sayi, List<long> asallar) { if (sayi > 1) { bool asal = true; int maxi = 0; long sayiKok = (long)Math.Sqrt(sayi); foreach (long l in asallar) { if (l <= sayiKok) { maxi++; } else { break; } } for (int i = 0; i < maxi; i++) { if (sayi % asallar[i] == 0) { asal = false; break; } } return asal; } else { return false; } } Bu 100 ms'lik fark nereden kaynaklanıyor olabilir? Kodumda değişiklik yapılması gereken yerler mi var acaba? Kullanım; Stopwatch sw = Stopwatch.StartNew(); long l = ninciAsal(10000);//kendi fonksiyonum sw.Stop(); Console.WriteLine(ninciAsal(10000)); Console.WriteLine("Found in : " + sw.ElapsedMilliseconds.ToString()); sw.Restart(); List<long> allprms = allPrimes(l);//sitedeki algoritmanın C#'a dönüştürülmüş hali (olduğu kadar) sw.Stop(); Console.WriteLine(allprms[allprms.Count - 1]); Console.WriteLine("Found in: " + sw.ElapsedMilliseconds); While loopunda sadece 1 ekliyorsun 2 eklemek yerine. asallar.Add(2) deyip l i 3 ten baslatirsan while dongusunun icindede l i 2 ser 2 ser arttirirsan algoritma hizlanir gibi duruyor. 2. olarak ise asal methodunda foreach loop ile for loopun var. For loop gereksiz duruyor. Foreach loopunda yapmak istedigini direkt yapmalisin gerek yok maxi yapip saymaya. Yapicagini orada yap (sayi buyuk mu check et, daha sonra bolunuyor mu onu check et) Teşekkür ederim, deniyim, bir de okulda bir derste (Discreate Math di galiba) bir algoritmanın çalışma süresi ile ilgili birşey öğrenmiştik. Döngüler, tekrar edilen şeyler polinom olarak yazıp (iki iç içe döngü sanırım n^2 olarak yazılıyordu [ikisi de n kere dönüyorsa]), matematiksel işlemleri vs. constant olarak varsayıp işlem yapıyorduk (ve hesaba katmıyorduk, ama buradaki süre ölçerler herşeyi hesaba katıyor dolaylı olarak). Demek istediğim, bu süreler sadece bir deney sonucu, mesela benim kodum diğer algoritmadan çoğu denememde yaklaşık 100-150 ms uzun sürüyor ama belki de matematiğini yapsam, n sayısı çok büyüdüğünde 2 katı 10 katı vs. uzun sürecek. Dolayısıyla bu sürelere güvenmeli mi, yoksa oturup matematiksel hesabını mı yapmalı? Sitedeki algoritmaların mantığı çok anlaşılır da burada paylaşılan o efsane kodu çözemedim, adresleme bilgimden kaynaklanıyor olabilir * ve & gördüğüm yerde bi korku basıyor, açıklaması var mıdır bi yerde? Edit: efsane kod şu konudaymış kafa gitmiş; http://forum.donanimhaber.com/m_98945826/tm.htm

Sorunun hacmine gore degisir bu soru. Yeri gelir bir sorun icin bir algoritma kurman gerekir bu algoritma O((n^2)/1000) olabilir ve baskasi gelipte sana benim O(n*10000) algoritmam var seninkisinden daha iyi diyebilir. Fakat gercek hayatta ancak n = 10000000 iken bu iki algoritmanin calisma suresi birbirine esit olur cunku (10000000^2)÷1000 = 10000000*10000. Eger sen elindeki listenin 10 milyon elemandan az oldugunu surekli ispatlarsan o zaman constant degerleri ele alabilirsin, fakat bunu ispatlayamazsan o zaman O(n^2) ile O(n) karsilasitmasi olur, bu yuzdende 2. algoritma daha hizlidir deriz (cunku n sonsuza gider).
Kendi yaptigin surelerin karsilastirmasiyla asymptotic complexity nin karsilasitirmak dogru olmaz. Birde o sitedeki kullanilan dil senin kullandigin dilden farkli olabilir, donanimda farkli olabilir. Ornegin dedigin gibi matematiksel islemleri saymayiz, fakat senin islemcin bir matematiksel islemi constant zamanda yapamazken karsi tarafinki yapabiliyor olabilir. Eger mantikli bir karsilastirma yapmak istiyorsan n sayisini al(atiyorum 100) bunun zamanini al (atiyorum 1 saniye) simdi x sayisi al (atiyorum 1000) n*x in zamanini al (atiyorum 10000 saniye) n*x in zamanini n e bol (10000 saniye) o zaman diyebiliriz ki bu yapilan testte karsi tarafin 100. sayiyla 100000. ci sayinin orani a dir. Bu orani kendi sonucunla karsilastir, yakin bir sonucsa algoritmanin runtime complexity si buyuk ihtimalle aynidir, x sayisi ne kadar buyukse bu yakinliktan o kadar emin oluruz.