运行时间和内存

Question

如果您看不到函数的代码，但知道它需要参数。是否可以找到运行时间速度和内存。如果是这样你会怎么做。在这种情况下有办法使用 Big O 吗？

Answer 1

不，仅通过查看函数的参数是不可能找到函数的内存或性能的。例如，相同的函数

void DoSomething(int x, int y, int z);

可以实现为 O(1) 时间和内存：

void DoSomething(int x, int y, int z) { }

或者实现为一个非常非常昂贵的函数，需要 O(x*y*z)：

void DoSomething(int x, int y, int z)
{
  int a = 0;
  for (int i = 0; i < x; i++) {
    for (int j = 0; j < y; j++) {
      for (int k = 0; k < z; k++) {
        a++;
      }
    }
  }
  Console.WriteLine(a);
}

以及许多其他可能性。因此，无法得知该功能的成本有多高。

Answer 2

我可以运行该函数吗？多次？

我将使用一系列参数值执行该函数，并测量每次运行的运行时间和（如果可能）内存消耗。然后，假设该函数采用 n 参数，我会将每个数据点绘制在 n+1 维图上，并从那里寻找趋势。

Answer 3

首先，这是一个面试问题，所以你最好不要说不。

---

如果我参加面试，这就是我的方法。

我可能会问面试官一些问题，因为面试是互动的。

因为我看不到代码，所以我想我至少可以多次运行它。这是我的第一个问题：我可以运行它吗？ （如果我无法运行它，那么我实际上什么也做不了，然后我就放弃了。）

该函数的用途是什么？如果函数编写得合理的话，这可能会提示复杂性。

论证的类型有哪些？有些是原始类型吗？尝试它们的一些组合。其中一些是否“复杂”（例如容器）？尝试一些不同尺寸的组合。其中一些是否相关（例如，一个与容器相关，另一个与容器的大小相关）？可以保存一些测试运行。另外，我希望给出论证的合法范围，这样我就不会浪费时间在非法猜测上。最后，测试一些边缘案例可能会有所帮助。

Answer 4

你能用代码运行该函数吗？像这样的东西：

start = clock();
//call the function;
end = clock();
time = end-start;

Answer 5

作为一个面试问题，你永远不应该回答“不，这是不可能的”。

您需要的是运行代码的能力。一旦可以运行代码，使用不同的参数调用相同的函数并测量所需的内存和时间。然后您可以绘制这些数据并获得良好的估计。

对于大 O 类型符号，您也可以遵循相同的方法并根据数据集大小绘制结果。然后尝试使用最小二乘拟合将该曲线与已知的复杂度曲线（如 n、n^2、n^3、n*log(n)、(n^2)*log(n) 等）拟合。

最后，请记住所有这些方法都只是近似值。

Answer 6

不，你不能，这将解决 停止问题 ，因为代码可能会无限运行 O(infinity) 。因此，解决这个问题也就解决了惠普，这当然被证明是不可能的。