Ho scritto un semplice programma in java per creare e mantenere i Dynamic Array:
public class DynamicArrays {
private Integer[] input = new Integer[1];
private Integer length = 0;
private Integer capacity = 1;
/**
* Big O Analysis of add:
* 1+1+addBulk
* 2+O(n)
* So it seems add is an O(n) operation!
* But add is only called when capacity is full and how many times can that happen?
* Let's say there are 8 elements added.
* so capacity will become full after 1st, 2nd, 4th additions. so its is Log(n) times?
*/
public void add(Integer i) {
input[length] = i;
length++;
if(capacity <= length)
addBulk();
}
/**
* Big O: O(n)
*/
public void addBulk() {
Integer[] newInput = new Integer[2*capacity];
for(int i=0;i<input.length;i++)
newInput[i] = input[i];
input = newInput;
capacity = capacity*2;
}
}
Ora mi chiedo qual è la complessità temporale dell'operazione di aggiunta? Se addBulk () non viene chiamato, è O (1). Altrimenti è O (n) perché addBulk () copia tutti gli elementi. Tuttavia addBulk è chiamato log (n) volte dell'input totale.
Quindi la complessità O (n * log (n))?
Ho anche letto da qualche parte che la complessità ammortizzata dell'addizione di array dinamici è O (2 * n), quindi O (n). Non potrei riferirmi a quel punto dal codice.
Puoi chiarire?