artificial-intelligence - 这个算法问题的时间复杂度是多少？

* 一种搜索方法的时间复杂度为 O(n2)，其中 n 是要搜索的空间中的状态数。如果搜索一千个状态的空间需要 1 秒，那么搜索一百万个状态的空间大约需要多长时间？*

我发现它大约需要 12 天，但我认为我发现的方式是非常错误的。我做了 100 万 ^2 / 86400（一天中的秒数）并找到了 11.56，所以大约 12 天。有没有更好更有效的解决方案？

标签： artificial-intelligencebig-o

几乎没有足够的信息来回答这个问题。请参阅Big-O 描述。

O(N^2)仅表示算法的执行时间将由 N^2 项支配。随着 N 变大，两个执行时间之间的比率将逐渐接近它们比率的平方。它没有说明特定值的执行时间。

让我们保持简单，假设设置开销与数组初始化O(N)和一些系统启动，一个常数。这使得执行时间

t = a * N^2 + b * N + c

对于 a、b 和 c 的某些值。即使我们知道这是方程形式，我们也没有足够的信息来解决仅给定一个 ( t, N) 数据点的问题。我们没有足够的知识来推导t.N= 10^6

我怀疑提出这个问题的人正在寻找无效的解决方案，做出无根据的假设，即 N=1000 已经使所有较小的项变得无足轻重。在这种情况下，只需按大小比的平方放大：

N1 / N2 = 10^6 / 10^3 = 10^3
Scale up by N^2, or (10^3)^2 = 10^6

这给了你 10^6 秒，或者一天多一点；我会把数学留给你。