B-albero di revisione

Question

Se siamo alla ricerca di incroci di linea (solo linee orizzontali e verticali) e abbiamo n linee con la metà di loro verticale e senza intersezioni poi

Ordinamento l'elenco dei punti di fine linea sul valore y avrà N log N utilizza mergesort

Ogni inserto cancellare e consultare i dati del nostro structue (supponendo che il suo un b-albero) sarà

in modo che il tempo di ricerca totale sarà N log N

Quello che mi manca qui, se il tempo per ordinare utilizzando Mergesort richiede un tempo di N log N e inserire ed eliminare richiede un tempo di

Grazie

Answer 1

La notazione O-grande descrive il comportamento asintotico dell'algoritmo. Cioè, si descrive il comportamento dell'algoritmo come N tendenze verso l'infinito. La porzione di algoritmo che prende N Registro N tempo farà impallidire la parte di algoritmo che prende registro N di tempo. Il significato del registro N diminuisce porzione relativamente niente come N diventa grande.

Answer 2

Ho il sospetto che il tutor si riferisce al problema della segmento linea Intersezione , che è più complesso della semplice classificare i segmenti. Noterete che questo articolo fa riferimento l'algoritmo Shamos-Hoey, che utilizza un albero binario per memorizzare i segmenti di linea ed efficiente rilevare intersezioni.

Michael è corretta in quanto utilizza un albero binario è inutile per una tantum sorta di segmenti di linea. Tuttavia, nel contesto di rilevare intersezioni, ordinamento seguiti da una ricerca produrrà prestazioni quadratica e non è l'approccio migliore, quindi, perché algoritmi di rivelazione pubblicitari utilizzano alberi binari.

Ad esempio, si supponga di ordinare i segmenti di linea lungo l'asse x da sinistra a destra. Un algoritmo di rilevamento naive sarebbe allora qualcosa come:

for (int i=0; i<segs.length - 1; ++i) {
  boolean searching = true;

  for (int j=i+1; j<segs.length && searching; ++j) {
     if (segments overlap on x-axis) {
       // Check for intersection.
     } else {
       // No overlap so terminate inner loop early.
       // This is the advantage of having a sorted list.
       searching = false;
     }
  }
}

A causa del ciclo doppiamente nested caso peggiore è O (n ^ 2) e si verifica quando tutti i segmenti di linea sovrappongano l'asse x. Il caso migliore è lineare e si verifica quando nessuno dei segmenti sovrapporsi a l'asse x.

Si potrebbe desiderare di iniziare implementando l'algoritmo ingenuo seguito da uno che utilizza una struttura B-tree.