algorithm - 该算法的复杂性

Question

所以我有一个这样的算法：

for i=0:360

 C...

 for j=0:a_j[i]

   C...

   for t=0:a_t[i][j]

     C...
   end
 end
end

所以我有三个循环，但两个内循环都取决于外循环的值。如何测量它的大 O 符号复杂度？

另外，如果我在这些循环之间有内存分配怎么办？它们算作Cs吗？

Answer 1

您没有对其余代码说任何话，因此假设其余部分是具有恒定复杂性的原始操作。

如果两个数组的条目小于一个常数值，那么复杂性就是O(1)——处理不依赖于从代码外部输入的任何值。如果它们是输入变量的函数，那么复杂性取决于将它们处理到这些数组中的函数，在这种情况下，您必须更具体。

Answer 2

我不确定到底是a_j什么a_t。如果a_j和a_t是常数，那么复杂度是O(1)。如果a_j和a_t是n，这可能意味着输入变量，那么我们必须计算复杂度。

总之，这个程序的复杂性是由你如何定义a_j和决定的a_t。

无论如何，我可以计算出你的程序执行了多少循环。

这是用python编写的代码：

ret = 0
for i, v in a_j:
    ret += v * sum(a_t[i])
if not ret: ret = 1
ret *= 360

希望能帮助到你。