計算大O運行時間

Question

您好，我無法找到的運行時間，該算法與下面的假設，S = O（logn）時間和Random_Integer的運行時間是恆定的時間：

1 express N-1 as 2^t * u where u is odd: 
    2 for i <-- to s do 
    3 a <-- Random_Integer(2, N-2); 
    4 if EuclidGCD(a, N) not equal to 1 then 
    5   return false; 
    6 x sub 0 <-- a^u mod N; 
    7 for j <-- 1 to t do 
    8  x sub j <-- x^2 sub j-1 mod N; 
    9 if x sub j = 1 and x sub j-1 not equal to 1 and x sub j-1 not equal to N -1 then 
    10  return false; 
    11 if x sub t not equal to one then 
    12  return false; 
    13 return true; 

從開始內循環指數模態運算需要n^3次，循環運行n次，總共n^4。然後按照我的方式進入outter循環，我們有另一個指數模態操作，它需要n^3次，然後EuclidGCD也需要n^3次。最後，outter循環也運行n次迭代。我相信這些數值是正確的，但是我對如何獲得總運行時間感到困惑。我也很困惑，如果這兩個嵌套的循環運行時間應該相乘，並且外部循環中的方法調用ExtendedEuclid應該與outter循環的運行時間相乘。我希望這是明確的感謝您的任何幫助。

Answer 1

內部循環是n^4（外部循環內部最慢的部分），並且對於外部循環的每次迭代運行一次，即EDIT：logn times，因此n^4logn。

無論其...

根據多久return false早早到達，它可能只爲n^5在最壞的情況下，例如如果幾乎所有的時候你在第一次迭代中返回false，那麼你只花了n^3-n^4的工作量，所以你的平均值爲O（n^3）或O（n^4） （取決於它是哪個return false）。