Question

使用大O表示法时，下面的操作需要多长时间？

根据数组包含的元素创建一个乘法表，即如果数组为[2,3,7,8,10]，首先将每个元素都乘以2，再将每个元素都乘以3，然后将每个元素都乘以7，以此类推。

个人答案与标达不一致，希望大佬们能够解答为什么是这个结果，谢谢！

Answer 1

答案是O(n**2)。
按照分而治之的思路，先对[2, 3, 7, 8, 10]中每个元素都×2，这意味着这一层调用栈要遍历所有元素，也就是O(n)个。×2结束后，继续对数组进行×3，意味着第二层栈同样要操作O(n)个元素...
以此类推，而因为数组有5个元素，∴总共要×5次，意味着调用栈的层数有O(5)层。
所以共需要操作5×5，那么这种乘法表的算法时间可归纳为O(n)×O(n)，也就是O(n**2)。

Answer 2

假如是用n衡量输入规模的话： (3) O(n) (4) O(√n) (5) O(n^3) (6) 因为不含n，所以是O(1)