當前位置:成語大全網 - 書法字典 - 分析add()函數的時間復雜度

分析add()函數的時間復雜度

當我

當I》= len時,即i = n時,for循環復制數組,因此只有1次的時間復雜度為O(n);

因此:

該算法的最佳時間復雜度為O(1);

最壞情況時間復雜度為O(n);

平均案件時間復雜性,

第壹種計算方法:(1+1+...+1+N)/(N+1)= 2n/(N+1)註:公式中,1+65438+。

第二種計算方法(加權平均法,也叫期望值):1(1/N+1)+1(1/N+1)...+1 (65438)

第三種計算方法(時間復雜度分攤):前n次運算的復雜度為O(1),第n+1次運算的復雜度為O(n),因此如果將最後壹次運算的復雜度分攤到前n次運算上,則每次運算的復雜度為O(1)。