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

Question

我是C++初学者，正在学习算法分析:我正在编写一个方法，该方法返回一个二维数组的行号最多为 1，输入数组中的每一行都已排序，并且当所有 1 都排序到前面时命中 0，如

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) 和 Big-Oh 符号。如果可能，该方法应该在 O(n) 时间内运行(而不是 O(n^2) )

Answer 1

This是您如何评估代码的运行时复杂性。对于您的代码，最坏情况下的复杂性将是矩阵的大小(即，如果您的代码编译)在 end 为 false 时 row 和 column 等于矩阵的大小。