पास्कल त्रिभुज एल्गोरिदम

Question

की समय जटिलता क्या होगी निम्नलिखित समस्या को हल करने के साथ कार्य (पास्कल त्रिकोण) जो इस तरह दिखता है।

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

मैं सफलतापूर्वक क्रियान्वित कर चुके हैं (नीचे देखें), लेकिन मैं एक कठिन समय पता लगाना क्या समय जटिलता इस समाधान के लिए किया जाएगा हो रही है। सूची द्वारा परिचालनों की संख्या 1 + 2 + 3 + 4 + है .... + n ऑपरेशन की संख्या एन^2 को कम करेगी गणित कैसे काम करता है और बिग-ओ नोटेशन में अनुवाद करता है?

मैं इस सोच रहा हूँ गॉस सूत्र n के समान है (n + 1)/2 तो O (n^2) लेकिन मैं गलत हो सकता है किसी भी मदद की बहुत सराहना कर रहा है

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

जटिलता O(n^2) है ।

आपके कोड में तत्व की प्रत्येक गणना निरंतर समय में की जाती है। ArrayList एक्सेस निरंतर समय संचालन, साथ ही सम्मिलन, निरंतर निरंतर समय है। Source:

आकार, isEmpty, मिलता है, सेट, इटरेटर, और listIterator संचालन निरंतर समय में चलाते हैं। एडी ऑपरेशन अमोरिज्ड निरंतर समय

आपके त्रिकोण में 1 + 2 + ... + n तत्व हैं। यह arithmetic progression है जो n*(n+1)/2 पर है, जो O(n^2)