Neden TreeSet Iteration O (n) O (n * logn) yerine?

TreeSet için zaman karmaşıklığı hakkında bir previous question okudum ve cevap O (n) zamanı almasıydı. Ancak, neden O (n) 'nin O (n * nlogn) yerine yinelemesini anlamıyorum. çünkü (n) ONeden TreeSet Iteration O (n) O (n * logn) yerine?

while (iterator.hasNext()){ //Runs N times 
    System.out.println(iterator.next() + " "); //each next is O(logn) 
}

o (* logn n) Ç olacağın için beklenir değil:

Her bir sonraki çağrı Böyle bir TreeSet yinelemenize eğer O(logn) time

Yani sürer while döngüsünde N yineleme vardır ve her bir iterator.next() çağrısı O (logn) süresini alır.

kaynak

2016-04-14 Eric S

Neden 'iterator.next()' O (log n) 'dir. Sadece bir sonraki düğüme gitmesi gerekiyor, bu O (1) değil mi? Kaynak koduna bakarak –

@JoseLuis doğru değil. –

@ louis-wasserman Haklısınız, çok üzgünüm. Iterator() 'ın sıralanmış düğümlerle bir liste döndürdüğünü ve sonra bir sonraki düğüme gitmenin kolay olduğunu düşünmüştüm. –

Bir next işlemi için en kötü durum, O(log n) işlemidir, çünkü bu ağacın yüksekliği. Bununla birlikte, ortalama olarak, bir sonraki eleman O(1) zamanında bulunabilir. Bunun nedeni, özdeki tüm geçişin n-1 ağaç kenarlarının her birini iki kez kullanmasıdır.

kaynak

2016-04-14 20:57:02

Iterator.next kodunun TreeMap.Entry.successor() 'da görüneceği anlaşılıyor: http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/6- b14/java/util/TreeMap.java # TreeMap.successor% 28java.util.TreeMap.Entry% 29 Evet, bir sonraki girişin sadece "p.left! = null" olması beklenir. Ancak, Big-O en kötü durum değil, ortalama değil mi? – markspace

@markspace Big-O, karmaşıklık açısından değil, işlevlerin büyümesi ile ilgili olduğundan, istediğiniz her davranışı tanımlar. Yüksek olasılıkla ortalama, en kötü, amortize edilmiş, beklenen maliyeti tanımlayabilirsiniz. Bu durumda, birlikte tüm işlemler için Theta (n) (en kötü ve en iyi durum) bile. Tek bir halefi bulmak, günlük kaydı maliyetine mal olabilir, ancak tüm n unsurlarını en fazla 2n olarak yineleyebilir. –

@markspace Detaylandırılmadan bağlanmış büyük-O, en kötü durum çalışma süresine karşılık gelir, ancak büyük O harfi, yalnızca bir işlevle ilgili bir matematik ifadedir. –

Böyle bir ağaç için yineleme uygulayabilirsiniz: function baskı toplam yineleme süresi O (K) yani her düğüm için sadece bir kere çağrılan olacak

void print(Node n) { 
    if (n.left != null) print(n.left); 
    System.out.println(n.value); 
    if (n.right != null) print(n.right); 
}

. Aynı algoritmayı yinelemeli olarak (yineleme olmadan) uygulayabilirsiniz. Yeterince dikkatli olursanız yineleme durumunu devam ettirmek için bir sınıfa sahip olabilirsiniz ve .next() çağrıldığında ilerleyebilirsiniz. println s arasındaki fonksiyon çağrılarının sayısının eşit olmadığı doğrudur, ancak genel olarak baktığınızda bunların tam olarak N olduğunu göreceksiniz.

kaynak

2016-04-15 07:26:37 Sorin

Neden TreeSet Iteration O (n) O (n * logn) yerine?

cevap

İlgili konular