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

Question

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

我有一个有 2 张地图的程序。在添加到其中一张地图之前，我会遍历每个字符并随机更改大小写。我只是将字符串放入另一张地图（无操作）

如果插入地图的大 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)。