解释此递归功能的时间复杂性（大O）
这是AlgoExpert的实践问题。输入是一个“特殊”数组，是一个非空数阵列，包含整数或其他“特殊数组”。 “特殊”阵列的产品总和是其元素的总和，其中将其内部的“特殊”阵列求和，然后乘以它们的深度水平。
O(n) time, where n is the total number of elements in the array
O(d) space, where d is the greatest depth of "special" arrays in the array
O(d) space
def productSum(array, multiplier=1):
sum = 0
for element in array:
if type(element) is list:
sum += productSum(element, multiplier + 1)
else:
sum += element
return sum * multiplier
我不明白为什么此功能的时间复杂性是o（n）？
如果您要在for语句中迭代的元素是另一个数组，那么语句o（n^2）中的语句不是吗？
或者，我想语句的内心，数组的长度未知.....
但我仍然不明白为什么只是o（n）。如果您获得每个单个元素是数组的输入，并且所有这些内部数组长度甚至比初始输入阵列长度更长，该怎么办？
还是这是一些摊销的分析内容？
谢谢！
This is a practice problem from AlgoExpert. Input is a "special" array that is a non-empty array that contains either integers or other "special arrays". The product sum of a "special" array is the sum of its elements, where "special" arrays inside it are summed themselves and then multiplied by their level of depth.
O(n) time, where n is the total number of elements in the array
O(d) space, where d is the greatest depth of "special" arrays in the array
O(d) space
def productSum(array, multiplier=1):
sum = 0
for element in array:
if type(element) is list:
sum += productSum(element, multiplier + 1)
else:
sum += element
return sum * multiplier
I don't understand why the time complexity of this function is O(N)?
If the element you're iterating through in the for statement is another array, then isn't it a for statement within for statement O(N^2)?
Or, I guess the inner for statement, the length of the array is unknown.....
but still I don't understand why it's just O(N). What if you get an input where every single element is an array, and all those inner array lengths are even longer than initial input array length?
Or is this some amortized analysis stuff?
Thanks!
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
这是一种线性时间算法，因为它的运行时间是在输入大小n中线性的。观察到原始输入阵列是[a，b，c，d]，其中a，b和c是整数，d是阵列[d1，d2，d3，d4，d5]，则总长度为n原始输入中的不为4（每个元素的字节数），而是在3+5 = 8的顺序（乘以每个元素的字节数）。通常，您的算法对每个元素进行恒定的工作，因此，对于长度n的每个元素，在时间O（n）中运行（一个元素可以是整数或数组本身），因此在时间O中（n） ）对于长度n的输入。
有一个嵌套的前面，但是递归深度可以大于2。例如，输入可以是[1,2,3，[4,5，[6，[1,2]]]，]，]，]本质上，循环的四倍nest。
在所有大小n的输入上，算法的运行时间t（n）定义为最糟糕的运行时间。输入尺寸n是表示输入所需的位数。原始输入中的一个元素是n大小n的子阵列，它不会消耗一个空间单位，而是空间的o（n）单位。
This is a linear time algorithm because it's running time is linear in the input size n. Observe that if the original input array is [a,b,c,d], where a,b, and c are integers, and d is the array [d1,d2,d3,d4,d5], then the total length n of the original input is not 4 (times the number of bytes for each element), but is on the order of 3+5=8 (times the number of bytes for each element). In general, your algorithm does a constant amount of work for each element, and hence runs in time O(n) for each element of length n (an element could be an integer or an array itself), and hence in time O(n) for an input of length n.
There is a nested for-loop, but the depth of recursion can be larger than 2. For example, the input can be [1,2,3,[4,5,[6,[1,2]]]], which essentially amounts to a quadraply-nested for loops.
The running time T(n) of an algorithm is defined to be the worst-case running time, over all inputs of size n. The input size n is the number of bits needed to represent the input. An element in the original input that is a subarray of size n will consume not one unit of space but O(n) units of space.