SORU
6 NİSAN 2010, Salı


Zaman karmaşıklığı Eratosthenes algoritması Elek

Wikipedia:

Algoritma karmaşıklığı O(n(logn)(loglogn)) bit işlemleri.

Nasıl o geliyor musun?

Karmaşıklığı loglogn terim içeren sqrt(n) bir yerde olduğunu söyledi.


Sanırım ben çalışan elek ilk 100 Sayı (n = 100), varsayarak, işaretli sayılar olarak kompozit alır sabit zaman (dizi uygulama), kaç kez kullanıyoruz mark_composite() olacak bir şey gibi

n/2   n/3   n/5   n/7   ...   n/97        =      O(n^2)                         

Ve bulmak için bir sonraki asal sayı (örneğin atlamak için 7 sonra karalanan tüm sayılar katları 5), sayı operasyonlar olurdu O(n).

Yani, bu karmaşıklığı O(n^3) olurdu.Kabul ediyor musun?

CEVAP
6 NİSAN 2010, Salı


  1. N/2 n/3 n/5 n/97 terim sayısı sabit olmadığı için(n) değildir. [Sonra düzenleme: O(n2çok gevşek bir üst ilişkilidir.] Gevşek üst sınır n(1 1/2 1/3 1/4 1/5 1/6 ...1/n) (...toplamıtüm(n günlük n): Sayılar n) Harmonic number bkz. Üst sınır daha uygun olur asal sayılar(n log n) olan n kadar buluruz toplamıdır n(1/2 1/3 1/5 1/7 ...),. (here here.)

  2. "Bir sonraki asal sayıyı bul" az ileride bir sonraki numarayı bulmak için hareket edecek genel olarak sadece O(n), amortized — sadece n zamanlardatoplamadım başına değil. Algoritma bu kısmı sadece O(n) alır.

(N log n) O(n) = O(n log n) bağlı bir üst aritmetik olsun bu iki kullanma işlemleri. Eğer Kont bit işlemleri, beri uğraşıyormuşsun ile sayılar için n, onlar hakkında günlüğü n bit olan faktör günlük n gelir, veren O(n log n log n) bit işlemleri.

Bunu Paylaş:
  • Google+
  • E-Posta
Etiketler:

YORUMLAR

SPONSOR VİDEO

Rastgele Yazarlar

  • ColdfusTion

    ColdfusTion

    3 Aralık 2007
  • Dellbear816

    Dellbear816

    4 Mart 2008
  • Distractify

    Distractify

    1 Aralık 2011