具有多個參數的方法的大O分析

-1

我們正在學習計算機科學類的介紹中的效率分析，我在解決此問題時遇到了問題。具有多個參數的方法的大O分析

假設我有一個方法：

public static void foo(int[][] arr, int num1, int num2) { 
    for (int i=0;i<arr.length;i++) { 
    arr[0][i] = num1*i; 
    } 

    for (int j=0;j<arr.length;j++) { 
    arr[i][0] = num2*i 
    } 
}

我的第一個問題是，如果我有一個方法，其中有3 for循環，但他們沒有嵌套，將增長率是多少？

此外，對於這種特定的製作方法，此方法的輸入大小是數組的面積？因爲每一個for循環從i = 0到i =陣列

最後的大小，如果

public static void fee(int[][] arr, double num1, double num2) { 
    num1=num1*Math.random(); 
    while (num1 == 0) { 
    num1=num1*Math.random(); 
    } 
    for (int i=0;i<num1;i++) { 
    //do something with arr 
    } 

    num2=num2*Math.random(); 
    while (num2 == 0) { 
    num2=num2*Math.random(); 
    } 
    for (int j=0;j<num2;j++) { 
    //do something with arr 
    } 
}

我怎麼會去尋找大O分析？

謝謝，我已經閱讀了多個關於查找大O的資源，但我仍然感到困惑。

來源

2014-11-24 rrpking

你的第一個方法不能編譯。 'arr [i] [0] = num2 * i'應該是'arr [j] [0] = num2 * j'。你的第二個方法也不能編譯 - 你應該把double賦給一個int - 並且如果num1或num2是0，它將無限循環。 – irrelephant 2014-11-24 00:18:13

對不起，我只是寫了很快提供一個想法，因爲我不能根據我的大學在網上發佈我的實際作業。 – rrpking 2014-11-24 00:24:19

我很確定你有'num2 == 0'它應該是'num2！= 0' – matts1 2014-11-24 00:31:37

在第一個例子中，如果您有3個非嵌套for循環（或者真的是任何類型的循環），它將簡單地爲O（x + y + z），其中x，y和z分別是每個循環的重複（假設內部持續時間）。但是，如果我們不知道哪個數字會成爲最大的，這個優勢就很重要。例如，如果我們知道x> y和x> z，我們可以簡單地說算法是O（x）（換句話說，我們知道它與x + y + z是線性的，但如果我們不' t知道x，y和z中哪一個是最重要的因素，所以我們不能簡單地說O（x）。簡單地說，嵌套=乘，不嵌套=加

在第二個例子中，由於無意識在下面的評論中已經說過了，非正式地說，在你提供的例子中它是O（無窮大）（但是，我會假設你的意思是while num2 != 0，因爲如果num2 = 0，另一個將會無限循環，然而，大O是最壞的情況，對於隨機數，最簡單的方法就是簡單地計算平均時間複雜度，時間複雜性的好處是如果你計算的比實際情況稍差，那麼沒有人水庫。

TLDR：平均時間複雜度約爲1000 + log_2 n，其中n爲num2。注意：儘管我們通常不會在時間複雜度計算中包含常數因子，但是當它們變得足夠大時，例如1000，它們可能成爲最重要的因素，尤其是因爲它很可能是因爲它們可能是最大的因子， 1000。

長解釋：因此，我們將0.5作爲平均乘數（雖然它實際上略差）。除以2的每個除法或者從尾數上取1位，或者從指數中減去1。位尾長度< <指數，所以我們只考慮指數。指數具有2^11的值，但是一半是正的，我們只希望是負的，所以2^10〜= 1000。爲了首先得到它，它將採取log2n，所以答案= 1000 + log2n

來源

2014-11-24 00:29:09 matts1

那麼，第二個例子是（非正式地）'O（∞）'。 – irrelephant 2014-11-24 00:44:18

您看看程序的功能，並根據您的輸入計算將執行多少個基本操作。有時候這種計算很簡單，有時很難。通常它涉及數學。數學很難。生活是艱難的。

在你的第一個例子中，你是否可以計算arr [0] [i]的賦值數量以及arr [j] [0]的賦值數量？

在第二個例子中，如果num1 * Math.random（）爲0，while循環執行的頻率如何？（答案可能是該代碼中的錯誤的指示）。

來源

2014-11-24 00:25:35 gnasher729

具有多個參數的方法的大O分析

回答

相關問題