time-complexity - 我可以将时间复杂度表示为总和（不同长度元素的复杂度）

Question

假设我必须遍历字符串数组中的每个字符，其中每个字符串都有不同的长度，arr[0].length != arr[1].length依此类推，例如：

#prints every char in all the array
for str in arr:
    for c in str:
        print(c)

这种性质的算法的时间复杂度应该如何表示？数组中元素的每个长度的总和？或者就像O(N*M)，将 N 作为元素的数量，将 M 作为数组的最大长度，它会相应地超出范围吗？

标签： time-complexitycomplexity-theory

Answer 1

有一种称为复杂性理论的精确数学理论可以回答您的问题等等。在复杂性理论中，我们有所谓的图灵机，它是一种计算机。然后将图灵机进行计算的时间复杂度定义为在自然数上定义的函数 f，使得 f(n) 是机器在长度为 n 的输入上的最坏情况运行时间。在您的情况下，它只需要将其输入复制到其他地方，这显然具有 O(n) 时间复杂度（n 这里是您的数组的组合长度）。由于 NM 大于 n，这意味着执行您描述的算法的图灵机运行时间不会超过某个恒定时间 NM，但由于数组元素长度的不规则性，它可能会更快停止。

如果你有兴趣了解复杂性理论，我推荐Michael Sipser的《计算理论导论》一书，它从头开始解释了这些概念。