C++：我如何計算一個方法的成本（算法分析）

我是C++的初學者和學習算法分析：我正在寫一個方法，它返回一個2d數組的最大行數爲1，每行從輸入陣列所有排序並擊中0時全爲1分的有幾分像C++：我如何計算一個方法的成本（算法分析）

1,1,1,0,0 
1,1,0,0,0 
1,1,1,1,0 
1,0,0,0,0 
1,1,1,1,1

前面的方法將從這個數組返回5和這裏是代碼：

int countone(int a[][]){ 
int count = 0, column = 0, row = 0, current = 0, max; 
bool end = true; 
do{ 
    if(a[row][column]==1) 
    { 
     current++; 
     column++; 
    } 
    if(a[row][column]==0) 
    { 
     column=0; 
     if(count<current) 
     { 
      count = current; 
      max = row; 
      current = 0; 
     } 
    row++;   
    if(a[row][column] != 1 && a[row][column] != 0) 
    { 
     end = false; 
     return max; 
    } 
} 
while(end)

代碼不是招沒有經過測試，所以它可能包含錯誤和錯誤，但這不是主要問題。我想知道這種方法的成本，但我不知道如何計算它。

我想要的成本是運行時間T（n）和大哦表示法。如果可能，該方法應該在O（n）時間內運行（而不是O（n^2））

來源

2012-03-07 Choi Shun Chi

定義成本。時鐘週期？緩存命中/未命中？執行時間處理時間？大O符號？ – Breakthrough 2012-03-07 13:21:06

成本取決於你的小時費率;-) – JRL 2012-03-07 13:23:22

你的問題是非常模糊的，但我會認爲在最壞的情況和平均情況下，通過計算任務，索引，增量的數量（這應該不會後bin後綴）將是要走的路。 – 2012-03-07 13:31:11

This是您如何評估代碼的運行時複雜性。對於您的代碼，最糟糕的情況是您的矩陣的大小（即如果您的代碼編譯）後end假當row和column等於矩陣的大小。

易於

來源

2012-03-07 13:31:32

我不認爲這是真的[複雜性是矩陣的大小]在這裏。我認爲它實際上是'O（無窮大）'，如果我理解正確的話 - 停止條件是一旦主菜單的值不是0/1，這是不能保證的[假設矩陣位於大小爲'2^n * 2^m'這只是memset（）'編爲0.雖然我可能會錯過一些東西... – amit 2012-03-07 13:33:56

我已經在答案中提到複雜性只有在'行'和「列」等於矩陣的大小。 – 2012-03-07 13:35:01

然後我誤解了你，並恢復我的評論。 – amit 2012-03-07 13:35:49

首先寫代碼的閱讀和理解

for(int row = 0; row < rowCount; ++row) { 
    for(int col = 0; col < colCount; ++col) { 
     if(a[row][col] == 0) { 
      if(max > col) { 
       max = col; 
       max_row = row; 
      } 
      break; 
     } 
    } 
}

是大致相同的，但你可以看到簡單的往往是如何執行的循環/語句（那是你實際上不會）。外循環運行rowCount乘以內部最多colCount時間（平均情況取決於）本身，但rowCount時間。

然後看看聲明花了多少錢。並將其與執行次數相乘（平均/最差的情況下，你喜歡什麼）。

說只有昂貴的操作是++。那麼你有rowCount * 1 (outer loop ++row) + rowCount * colCount * 1(inner loop ++col)。

，你會得到rowCount x (colCount + 1)

來源

2012-03-07 14:05:12 x539

感謝您的建議。但是，我的目標是使運行時間成本爲O（N）。如果存在雙「for」循環，那將是O（N^2）。 – 2012-03-08 06:41:15

如果rowCount和colCount是獨立的，你不能說它是O（N^2）。然後是O（N * M）。使用矩陣時，最佳解決方案是O（N * log（M））。但是，用一個簡單的數字數組O（N）是可能的。但是，如果N是矩陣中的場數，則問題已經在O（N） – x539 2012-03-08 10:49:07

您可以使用數組排序屬性來提高運行時間。沒有理由重新開始並從每行的第一列開始掃描。一旦你掃描完1，直到你輸入0，你就會知道任何後續的行都不會有更長的1字符串，除非它們在找到0的列中有1。您可以逐步遍歷矩陣，向右掃描直到達到0，然後向下掃描，直到達到1.停止一旦您點擊了陣列的右邊或底邊。

int maxRow = 0; 
    int i = 0, j = 0; 
    for (;;) { 
      if (a[i][j] == 0) { 
        // Try moving down one row 
        if (++i >= rowCount) break; 
      } else { 
        // New record row length 
        maxRow = i; 
        // Try moving over one column 
        if (++j >= colCount) break; 
      } 
    } 
    return maxRow;

請注意，輸出是基於0的，因此對於示例矩陣，結果將是行4（不是5）作爲具有最多1的行。

掃描的矩陣元素數最多爲：T（n，m）= n + m-1，即O（n + m）。如果矩陣是平方（m = n），那麼T（n）= 2n-1，即O（n）。

來源

2015-12-04 15:55:59

C++：我如何計算一個方法的成本（算法分析）

回答

相關問題