算法分析：大哦複雜度，作爲函數的快速輸出

Question

以下函數返回的值是多少？將你的答案表示爲n的一個 函數。使用O（）符號給出最糟糕的運行時間。

僞算法的代碼：

F1(n) 

    v = 0 

    for i = 1 to n 
     for j = n + 1 to 2n 
      v++ 
    return v 

我的方法：

F1（n）的輸出是從由內部的for循環中計算的變量v返回的整數值迭代大小爲2n，大小爲n的外部for循環。

變量v在兩個循環的迭代開始之前被初始化爲0。當第i個for循環在第1次迭代時，第j個for循環（內部for循環）從大小n + 1迭代到2n。假設n = 5，則第j個for循環從j = 6迭代到10，這意味着內部for循環的1次完整迭代v的次數增加。由於第j個for循環始終將v增加n-1（在這種情況下爲4），因此在每個完整迭代中，這意味着當第i個for循環從1開始到n時，變量v增加n-每次迭代1次。因此該算法映射函數g（n）=（n-1）*（n-1）。這將是4 * 4，所以當n = 5時v = 16。這是事實，因爲當n = 5時，每完整的第j次迭代v增加4.因此，如果第i個for循環從i = 1，...，4 （1到n），那麼每增加i，v就增加4，這就解釋了爲什麼結果是（n-1 * n-1）作爲答案。

該程序的最壞情況Big Oh複雜度爲O（n^2），因爲它具有嵌套循環結構，其中外部循環遍歷1至n次，內部循環遍歷n + 1至2n次這也相當於n次，因爲它遍歷n的所有值。

最後，變量的初始化/遞增需要O（1）次，所以與嵌套的for循環相比，這不會影響複雜性。

Answer 1

對我而言這個地圖g(n)=n^2函數自循環for i=1 to n運行n次，如果你計算範圍從[1,n]範圍內的所有值。當然，如果它是[1,n)那麼你有g(n)=(n-1)^2但這是約定的問題。

兩個嵌套循環，每個循環運行n次，給你O(n^2)複雜性，在這種情況下是最好的平均值 - 最差的。所以你的方法是好的，如果這是你的問題:)