c++ - 带有内部while循环的while循环:O(n)还是O(n ^ 2)?
问题描述
#include <unordered_map>
using namespace std;
int lengthOfLongestSubstring(string s) {
unordered_map<char, int> ht;
int max = 0;
int i = 0; int j = 0;
while (i < s.size() && j < s.size()) {
if (ht.find(s.at(j)) == ht.end()) {
ht.insert( {s.at(j), j} );
max = (j - i + 1 > max) ? j - i + 1 : max;
j++;
}
else {
int len = ht.at(s.at(j)) + 1;
while(i < len) {
ht.erase(s.at(i));
i++;
}
}
}
return max;
}
是时间复杂度O(n)
还是O(n^2)
?为什么?
我的直觉是它是 O(n),i 和 j 迭代相同的长度。
解决方案
它的:
- 严格来说:
O(2n)
,在最坏的情况下,您迭代输入大小的两倍; - 用渐近语言说话: ,因为忽略了
O(n)
常数因素。
推荐阅读
- macos - 如何在文件中的任何 `{` 和 `:` 字符中添加换行符
- python - Pycharm 中的解释器设置存在问题
- c# - c# 10000 x 10000 矩阵乘法
- css - Bootstrap 4.6 容器的子级仅使用半页高度
- c++ - 在函数模板中转换为否定的一元表达式失败
- javascript - Visual Studio 代码终端显示一些我不理解的消息
- swift - Swift 包管理器 SecureTransport 错误:连接因错误而关闭 (-1)
- sql - 在 SQL 中转换为数字
- load-balancing - AWS-ALB 未将流量转发到 EKS 上新添加的后端 pod
- python - Python 字典访问比列表索引访问更快