“算法 X 的成本在使用的最大椭圆区域内是线性的吗？”
这是否意味着算法 X 的成本随着椭圆面积的增加而线性增长？
请注意，椭圆的面积会增加一倍，这意味着呈指数增长，对吧？
问问题
122 次
2 回答
2
如果 A 是区域，则算法将为 O(A)。
如果您考虑 (x/a)^2+(y/b)^2=1 那么您的算法将是 O(a*b)
如果在算法的每次迭代中将椭圆面积加倍，则该面积将呈二次增长，但总复杂度将为 O(An)，其中 An 是上次迭代期间的面积
编辑
我会深入一点：
您的算法将执行 f=A0+A1+...+An 操作，其中Ai是第i 次迭代的区域，我们可以将公式重写为 f=A0+2*A0+4*A0+...+2^ n*A0
O(f) = O(2^n*A0) 其中 2^n*A0 = An
于 2013-07-01T21:00:27.960 回答
1
椭圆的面积是二次的 (N^2)，而不是指数的 (2^N)。该语句意味着成本是 N 的线性函数，其中面积是函数 N^2。
于 2013-07-01T20:26:38.677 回答