时间戳

首页 > 解决方案 > 循环遍历字符串列表然后还遍历每个字符串的每个字符的算法的时间复杂度是多少？

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

问题描述

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

伪代码示例：

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 来表征它们的所有长度。

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

标签： time-complexitybig-o

解决方案

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

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

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

推荐阅读