Sono altamente confuso nel calcolare la complessità temporale di un algoritmo di merge sort. In particolare sulla fase di divisione. Nella fase di divisione dobbiamo calcolare il punto medio di "n" cioè "q = n / 2".
Come ci vorrà tempo costante. Se supponiamo che la divisione sia un'operazione elementare e impieghi molto meno tempo, allora dovremmo includere anche il tempo impiegato dalla divisione.
Supponiamo di dover dividere una quantità molto grande di tempo quindi deve essere considerato mentre si calcola la complessità temporale. Secondo me il numero di divisioni dipende da "n", ad esempio il punto medio di calcolo dipende dalla dimensione dell'array "n".
Ad esempio,
if n = 2
Numero di divisioni richieste = 1
se n = 4
Numero di divisioni richieste = 3
if n = 8
Numero di divisioni richieste = 7
se n = 16
Numero di divisioni richieste = 15 e così via ....
Secondo me,
Se Definisci in modo ricorsivo: -
Numero di Divide necessario per "n" (input array length = n) < = 1 + Numero di divisioni necessarie per (n-1). {quando n = 0 Numero di divisioni = 0 quando n = 1 Number of divide = 0}
In alternativa ..........
Numero di divisioni necessarie per "n" (lunghezza dell'array input = n) < = (somma di 2 ^ i da 0 a n-1) - (2 ^ n)
Quindi, dipende da "n". Quindi, come possiamo prenderlo come un tempo costante ????
