c++ - 函数的行数

Question

采用以下函数和其他代码，对其进行编码，使其在运行时计算自己的行数。

typedef double Matrix[100][100];

void multiply(Matrix A, Matrix B, Matrix C, int n)
{
     //n is the actual matrix order
     for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
        {
            C[i][j] = 0;
            for (int k = 0; k < n; ++k)
                 C[i][j] += A[i][k] * B[k][j];
        } 
}

所以我很难理解我应该做什么。我不确定这个特定问题的行数是多少。如果有人能澄清我需要做什么，那将是一个很大的帮助，这就是我所要求的。

我被问到的问题:编写一个 main 将 int 变量 lc 初始化为零，并输入 n 来调整矩阵的大小。通过引用传递 lc 到 multiply 函数。让它作为执行的代码行数返回，并将其与 n 一起打印出来。您还应该将矩阵 A 和 B 初始化为希尔伯特矩阵(第 i-j 个条目为 1.0/(i + j + 1))。测试 n = 3，这样您的产品将是 3x3 希尔伯特矩阵的平方(只是为了确保您的代码有效)。然后，将其设置为运行两次:一次 n = 50，一次 n = 100。注意 n = 100 的时间，它应该是 n = 50 的大约 8 倍。

Answer 1

问题是“编写代码以便在运行时计算自己的行数”，这意味着“检测代码以便计算每一行代码”

如果从 0 到 9 计算 for 循环中执行的语句数，则 for 循环初始值设定项为 1，循环比较为 11(因为您为索引 10 比较一次以实现循环结束), 10 用于循环增量，10 用于循环中的每个内容语句。总计 32 与 10(循环的大小)成正比，因此复杂度为 O(N)

如果计算嵌套 for 循环中执行的语句数，其中两个循环都从 0 运行到 9，则外循环初始值设定项为 1，外循环比较为 11(因为您比较一次索引 10 到意识到循环已经结束)，外循环增量为10，外循环中每个内容语句为10:10*1用于内循环初始化器，10*11用于内循环比较，10*10用于内循环递增，循环中每条内容语句递增10*10。总计 352 与 10^2(循环大小的平方)成正比，因此复杂度为 O(N^2)

并且由于您的乘法函数具有从 0 到 n 的三个循环，因此复杂度为 O(n^3)

下面是我将如何检测代码来对语句进行计数:

#include <stdio.h>
#include <math.h>

#define N 10
int count=0;

void simpleloop()
{
  count=0;
  ++count;  int sum=0;               // 1   for this line
  ++count;  for(int i=0;             // 1   for this line
  ++count,      i<N;                 // N+1 for this line (i=0 through i=N   inclusive)
  ++count,      ++i)                 // N   for this line (i=0 through i=N-1 inclusive)
            {
  ++count;    sum+=i;                // N   for this line (i=0 through i=N-1 inclusive)
            }
  ++count;  printf("sum=%d\n",sum);  // 1   for this line
}

void nestedloop()
{
  count=0;
  ++count;  int sum=0;               // 1       for this line
  ++count;  for(int i=0;             // 1       for this line
  ++count,      i<N;                 // N+1     for this line (i=0 through i=N   inclusive)
  ++count,      ++i)                 // N       for this line (i=0 through i=N-1 inclusive)
            {
  ++count;    for(int j=0;           // N       for this line
  ++count,        j<N;               // N*(N+1) for this line N*(j=0 through j=N   inclusive)
  ++count,        ++j)               // N*N     for this line N*(j=0 through j=N-1 inclusive)
              {
  ++count;      sum+=i*N+j;          // N*N     for this line N*(j=0 through j=N-1 inclusive)
              }
            }
  ++count;  printf("sum=%d\n",sum);  // 1       for this line
}

typedef double Matrix[100][100];

void multiply(Matrix A, Matrix B, Matrix C, int n)
{
  count=0;
            // n is the actual matrix order
  ++count;  for (int i = 0;                      // 1         for this line
  ++count,       i < n;                          // n+1       for this line
  ++count,       ++i)                            // n         for this line
            {
  ++count;    for (int j = 0;                    // n         for this line
  ++count,         j < n;                        // n*(n+1)   for this line
  ++count,         ++j)                          // n*n       for this line
              {
  ++count;      C[i][j] = 0;                     // n*n       for this line
  ++count;      for (int k = 0;                  // n*n       for this line
  ++count,           k < n;                      // n*n*(n+1) for this line
  ++count,           ++k)                        // n*n*n     for this line
                {
  ++count;        C[i][j] += A[i][k] * B[k][j];  // n*n*n     for this line
                }
              }
            }
}

int main()
{
  printf("simpleloop:\n");
  simpleloop();
  printf("count=%d O(N^%d)\n\n",count,(int)log10(count/N)+1); // total counts = 3N + 4 -> O(N)

  printf("nestedloop:\n");
  nestedloop();
  printf("count=%d O(N^%d)\n\n",count,(int)log10(count/N)+1); // total counts = 3N^2 + 4N + 4 -> O(N^2)

  Matrix A={},B={},C={};
  printf("multiply:\n");
  multiply(A,B,C,N);
  printf("count=%d O(N^%d)\n\n",count,(int)log10(count/N)+1); // total counts = 3N^3 + 5N^2 + 4N + 2 -> O(N^3)

  return 0;
}

对语句的计数与对行的计数略有不同，因为 for 循环包含三个语句加上循环的内容。我认为它可以更好地衡量发生的事情的数量，但这并不是你的问题所要求的，所以如果你真的想要线，你将不得不从循环比较和循环增量中删除计数。复杂性将保持不变。