java - 我的程序中的大 O 复杂性是否正确

Question

我正在学习所有关于大 O 的知识，并且我试图了解我的每个程序的大复杂性。我想确保我的复杂性是正确的。

方案一：

第 1 步 - 从文件中读取所有单词O(n)，n 是词表的大小 第 2 步 - 遍历每个单词的字符并对其进行操作（我不会详细说明它的作用，它只是一个循环）-O(m)其中 m 是单词中的字符数第 3 步 - 插入 HashMapO(1)

全部的 -O(n + m)

程序 2： 步骤 1 - 将单词传递给程序步骤 2 - 在 hashmap 中查找单词 -O(1) 步骤 3 - 循环遍历每个单词的字符并对其进行操作O(m)，其中 m 是单词中的字符数 步骤 4 - 将单词输入一个函数 - 我计算得到O(2^m)，其中 m 是单词中的字符数 第 5 步 - 在 hashmap 中再次查找单词O(1)

O(2^m + m)

程序不涉及 O(n)，因为我只是在查找 hashmap。遍历传入单词的字符的唯一复杂性

Answer 1

遍历所有单词中的所有字符是 O(n*m)，其中 n 是单词数，m 是单词的最大长度

哈希图的插入和查找在技术上是 O(n) （如果所有元素散列到相同的值），但如果你的教授说它是 O(1) 那就去吧

在不知道函数是什么的情况下，我们无法帮助您完成“第 4 步 - 将单词输入函数”