方法調用

Question

http://imgur.com/a/efinr

所以我一直在負責創建與HugeIntegers該做的基本操作（加，減，乘）在Java方法（這是數組那家數字中的計算方法調用的時間複雜度在他們的索引中，例如1111就是[1,1,1,1]）。我們被要求分析它的時間複雜性（即Bigta複雜性類），並且在分析我的代碼的一部分時遇到了一些問題（請參閱鏈接）。我知道x1.add（diff）會給我很大的theta（n），其中n是HugeInteger的位數，compareTo（x2）也會給我很大的theta（n）。 while循環內的內容也是大的theta（n）。 現在，這段代碼的總時間複雜度是（n^3）的大θ還是n？2？我在while循環條件時遇到了一些麻煩，因爲我不確定n是應該添加還是相乘。我知道無論結果是什麼，它都會被乘以while循環中的n。

任何幫助是非常，非常感激。我一直堅持在這一週的好一段時間。

Answer 1

循環的條件將在每次循環迭代中運行一次。循環的內容也將在每個循環迭代中運行一次。所以你可以添加這些。然後，當然，乘以循環運行的次數。如果條件是（n）並且循環體是（n），那麼它們仍然是（n）。如果循環運行（n）次，那麼總數是（n^2）。