CODEWITHSUNDEEP
c++algorithm
Choi Shun Chi
Choi Shun Chi

Reputation: 93

C++ : How can I calculate a cost of a method (Algorithm Analysis)

I am a beginner of C++ and learning Algorithm Analysis: I am writing a method which return a row number of a 2d array has most 1's , each rows from the input array are all sorted and hits 0 when all 1's are sort to the front like

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

the method will return 5 from this array and here is the code:

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)

the code hasn't tested yet so it may contains bug and error, but this is not the main point anyway. I would like to find out the cost of this method, but I have no idea how to calculate it.

The cost I want is Running time T(n) and Big-Oh notation. If possible, the method should running in O(n) time ( not O(n^2) )

Upvotes: 4

Views: 4840

Answers (3)

Daniel Stevens
Daniel Stevens

Reputation: 772

You can make use of the sorted property of the array to improve the run time. There is no reason to start over and scan from the first column of each row. Once you've scanned through the 1s until you hit a 0, you know that any subsequent rows will not have a longer string of 1s unless they have a 1 in the column where the 0 was found. You can traverse the matrix in a stepwise manner, scanning right until hitting a 0, and scanning down until hitting a 1. Stop once you've hit the right or bottom edge of the array.

    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;

Note that the output is 0-based, so for the example matrix the result will be row 4 (not 5) as the row with the most 1s.

The number of matrix elements scanned will be at most: T(n, m) = n + m - 1, which is O(n+m).
If the matrix is square (m = n), then T(n) = 2n - 1, which is O(n).

Upvotes: 0

x539
x539

Reputation: 1014

First write code that is easy to read and understand

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;
        }
    }
}

is roughly the same, but you can see easy how often a loop/statement is executed(that is what you actually wont). The outer loop is ran rowCount times the inner at most colCount times(average case depends) for itself but that rowCount times.

Then look what statement costs how much. And multiply it with the number of times it is executed(average-/worst case what you like).

Say the only expensive operation is ++ with. Then you have rowCount * 1 (outer loop ++row) + rowCount * colCount * 1(inner loop ++col).

And you get rowCount x (colCount + 1)

Upvotes: 1

Pulkit Goyal
Pulkit Goyal

Reputation: 5654

This is how you can evaluate the runtime complexity of your code.For your code, the worst case complexity would be the size of your matrix (i.e. if your code compiles) after you make the end false when row and column equal the size of your matrix.

Upvotes: 2

Related Questions