0

如果我需要确定具有给定函数设置的成本的过程的算法复杂性，这只是给出 O(n^2 log n) 的问题 - 还是大 O 碰巧是什么？

另外，不是大 O 只是多项式中任何项的最高阶吗？如果要求我提供推导，我不确定要提供什么，因为这似乎有点微不足道。

最后一个问题，如果我需要给出算法的操作计数，这真的很简单——大致就像

array1, array2, array3 of size n 
for i in n:
    array2[i] = sqrt(array1[i])
    array3[i] = array1[i]^2

对于“操作计数”，我只是计算我所有的算术运算并找出哪些（如 sqrt）算作多个操作，等等......或者我可以写它是 O(n) 吗？

4

1 回答 1

0

流程的算法成本是流程所有组件的成本。例如，使用您的示例，我们可以分解所有事物的成本

array1, array2, array3 of size n

每个数组需要 n 时间，所以总共需要 3n 时间，在 O(n) 中。

for i in n:

这意味着循环中的所有内容都乘以 n。

array2[i] = sqrt(array1[i])

这需要 O(1) 时间。为什么？访问数组元素是常数时间。取 sqrt 是常数时间。并且设置数组元素的值是常数时间。所以整个操作是常数时间。

array3[i] = array1[i] ^ 2

这需要 O(1) 时间，原因与前面的操作相同。

所以整个运行时间是 3n + n * ( 1 + 1) （这里使用粗略的数学，不精确），这只是 O(n) 时间。这有帮助吗？

至于实际推导，有专门的技术。你学习过大哦符号的精确数学定义吗？

这个链接描述了大哦符号的正式定义，并提供了一个如何证明这些东西的例子。

于 2012-04-24T21:28:50.907 回答