Quale sarebbe la complessità temporale dell'algoritmo del triangolo pascal

Question

Compiuta la risoluzione del seguente problema (triangolo Pascal) che appare in questo modo.

[ 
    [1], 
    [1,1], 
    [1,2,1], 
    [1,3,3,1], 
[1,4,6,4,1] 
] 

ho implementato con successo il codice (vedi sotto), ma sto avendo un momento difficile capire che cosa la complessità temporale sarebbe per questa soluzione. Il numero di operazioni per elenco è 1 + 2 + 3 + 4 + .... + n il numero di operazioni si ridurrà a n^2 come funziona il calcolo matematico e si traduce in notazione Big-O?

Sto pensando che questo è simile al gauss formula n (n + 1)/2 in modo da O (n^2), ma potrei sbagliarmi ogni aiuto è molto apprezzato

public class Solution { 
    public List<List<Integer>> generate(int numRows) { 
     if(numRows < 1) return new ArrayList<List<Integer>>();; 
     List<List<Integer>> pyramidVal = new ArrayList<List<Integer>>(); 

     for(int i = 0; i < numRows; i++){ 
      List<Integer> tempList = new ArrayList<Integer>(); 
      tempList.add(1); 
      for(int j = 1; j < i; j++){ 
       tempList.add(pyramidVal.get(i - 1).get(j) + pyramidVal.get(i - 1).get(j -1)); 
      } 
      if(i > 0) tempList.add(1); 
      pyramidVal.add(tempList); 
     } 
     return pyramidVal; 
    } 
} 

Answer 1

complessità è O(n^2) .

Ogni calcolo dell'elemento nel codice viene eseguito in tempo costante. Gli accessi ArrayList sono operazioni a tempo costante, nonché inserimenti, tempo costante ammortizzato. Source:

Le dimensioni, le operazioni EVuota, ottenere, set, iteratore, e ListIterator gestiscono in tempo costante. L'operazione di aggiunta viene eseguita in tempo costante ammortizzato

Il tuo triangolo ha elementi 1 + 2 + ... + n. Questo è arithmetic progression che corrisponde a n*(n+1)/2, che è in O(n^2)