循环遍历字符串列表然后循环遍历每个字符串的每个字符的算法的时间复杂度是多少？

Question

我刚刚做了一个采访，我的解决方案涉及这个算法，但我不能自信地说时间复杂度是多少。

伪代码示例：

arr = ["hello", "this", "is", "some", "different", "length", "strings"]

function (arr)
    for string in arr
        for char in string
            // do stuff in constant time

我最初认为复杂度为 O(N * M)，其中 N 是数组的长度，M 是每个字符串的长度，但是如果字符串的长度不同，我无法用常数 M.

编辑：数组中的字符串不必是真实的单词，可以是任意长度的任意字符串

Answer 1

在这种情况下，您所做的工作量不仅仅取决于输入数组中的元素数量，还取决于这些元素的属性（即它们的长度），您正确的是，简单地将算法描述为线性或 O(n) 是不够的。

如果所有字符串确实都是任意长度，您可以在技术上将时间复杂度描述为 'pseudo-polynomial' 或 'pseudo-linear'。虽然字符串的长度是任意的（正如你所说，你不能给 'm' 一个固定的值），你仍然可以将复杂度描述为 O(nm) 其中 m 是长度输入中最大的字符串（m 是未知的还是任意的并不重要：你可以对 n 说同样的话）。说算法在 O(nm) 甚至 Θ(nm) 中对于 m 作为输入字符串的平均长度也是正确的。这些只是说它是伪线性的具体方式。

但是，如果您做出更多符合条件的假设或重新构建您解释为算法 'input' 的内容，那么您可以将其描述为线性。例如，如果您可以通过任何常量限制输入中任何字符串的最大长度（例如，如果您知道不会有超过 10,000 个字符的字符串），那么说该算法是 O(n) 将是完全正确的。您还可以说该算法与输入中的字符总数（而不是单词数）呈线性关系，或者与平均输入字符串长度呈线性关系。

循环遍历字符串列表然后循环遍历每个字符串的每个字符的算法的时间复杂度是多少？

What is the time complexity of an algorithm that loops over a list of strings and then also loops over each character of each string?

big-o

time-complexity