java - 在插入映射之前循环遍历字符串中的每个字符的大 O 表示法

Question

我是大 O 表示法的新手，并且在我的程序中对它有几个问题。

我有一个有 2 个 map 的程序。在添加到其中一张 map 之前，我会循环遍历每个角色并随机更改大小写。我只是将字符串放入另一个 map 中(没有操作)

如果插入映射的大 O 是 O(1)，如果我在将每个字符放入映射之前循环遍历它会怎么样？该程序的总大 O 复杂度是多少(将每个插入合并到映射中)？

Answer 1

如果有一个大小为 n 的字符串，并对其进行迭代，在内循环中执行 O(1) 插入，则时间复杂度为 O(n)。

为了让这个问题变得不那么简单，假设插入成本a(其中a可以是n的函数、常数或完全其他的东西)，然后总成本将为 O(an+a)。这是因为您在内循环中插入了 n 次，然后又对整个字符串插入了一次。在你的例子中，a=1，所以我们有 O(1n+1) = O(n)。