C ++: how can I calculate the cost of a method (analysis of algorithms)

Question

I start C ++ and study the analysis algorithm: I write a method that returns the row number from a 2d array, has at most 1, each row from the input array is sorted and removes 0 when all 1 are sorted by the front, as

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 has not yet been tested, so it may contain errors and errors, but this is not the main thing. I would like to know the cost of this method, but I have no idea how to calculate it.

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

Answer 1

This is how you can appreciate the complexity of executing your code. For your code, the worst difficulty will be the size of your matrix (i.e. if your code compiles) after you end false when row and column are the size of your matrix.

Answer 2

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

about the same thing, but you can easily understand how often the loop / statement is executed (this is what you really don't want). The outer loop is triggered by rowCount times when the inner value is not greater than the colCount time (the average case depends) for itself, but the rowCount time.

Then see which operator costs how much. And multiply it by the number of times it is executed (average / worst you like).

Let's say that only an expensive operation is ++. Then you have rowCount * 1 (outer loop ++row) + rowCount * colCount * 1(inner loop ++col) .

And you will get rowCount x (colCount + 1)

Answer 3

You can use the sorted array property to improve runtime. There is no reason to start and scan from the first column of each row. After you checked 1s until you hit 0, you know that any subsequent rows will not have a longer row from 1, unless they have 1 in the column where 0 was found. You can move around the matrix in stages, scanning right until you press 0 and scanning until you press 1. Stop as soon as you press 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 based on 0, so for an example matrix, the result will be row 4 (not 5) as the row with the most units.

The number of scanned matrix elements will be no more than: T (n, m) = n + m - 1, which is equal to O (n + m).
If the matrix is ​​square (m = n), then T (n) = 2n - 1 such that O (n).