以下算法的執行時間是多少？

Question

以下代碼返回給定數字n的所有素數因子。

算法背後

方法：

迭代數（即> = 2），直到N/I來獲得的素因子。

內部循環簡單地用當前的素數除以它，如果同樣的質數出現一次更會繼續將減少數量的大小。

if語句會添加最後一個& n> 2的最高素數，因爲到那時n已經減少到那個值。

static List<Integer> getAllPrimes(int n){ 
      List<Integer> factors = new ArrayList<Integer>(); 
      for(int i = 2 ; i <= n/i ; ++i){ 
       while(n % i == 0){ 
        factors.add(i); //LINE 1 
        n/=i; 
       } 
      } 
      if(n > 2){factors.add(n);} 
      return factors; 
} 

如何確定此算法的運行時間？由於每當內部循環迭代時，如果它是質數，它會根據索引i減小大小，並帶有一些常數值，如n/2，n/3 ....等等。

Answer 1

當分析這樣的算法，它往往有助於闡明你是否正在尋找一個最好的情況，平均情況，或最壞情況分析，因爲答案可能在每種情況下是不同的。

讓我們先從最壞情況分析。爲了讓這個算法儘可能長時間運行，會發生什麼？那麼，如果我們從不劃分任何主要因素，那麼外部循環將盡可能多次運行。具體來說，它將運行Θ（√ n）次。只有當問題數是素數時纔會發生這種情況，所以我們可以說最差的情況發生在素數輸入上，運行時爲Θ（√n）。

最好的情況怎麼樣？那麼，這個算法要麼會因爲n太大而終止，要麼n對於我而言太小。下降n比增加i快得多，因爲n以幾何方式下降，而我以算術方式增加。一個理想的情況是輸入儘可能快地下降，如果你提供的輸入只有微小的因素（這些被稱爲平滑數字），就會發生這種情況。在理想的情況下，你會得到兩個完美的力量，在這種情況下，該算法將n重複減半，直到它降到1.這是對數行爲的標誌，所以在最好的情況下，運行時間是Θ（log N）。