问时间复杂度
请问这段代码的时间复杂度是多少int lengthOfLongestSubstring(char * s){
int hash = {0}; // 模拟哈希表
int max = 0; // 最大值
for(int i = 0, j = 0; i < strlen(s); i++){
hash]++;
while(hash] > 1) hash]--;
max = max < (i-j+1)?(i-j+1):max;
}
return max;
} 这段代码的时间复杂度是 O(n)，其中 n 是字符串 s 的长度。具体分析如下：
1. 初始化哈希表的时间复杂度是 O(1)，因为哈希表的大小固定为 128。
2. for 循环的时间复杂度是 O(n)，因为它会遍历整个字符串 s。
3. while 循环的时间复杂度也是 O(n)，因为它最多会执行 n 次（即 j 最多增加到 i），并且每次执行时会对哈希表进行更新操作。
4. max 的更新操作的时间复杂度是 O(1)。
因此，总的时间复杂度是 O(n)。 isdkz 发表于 2023-9-21 16:51
这段代码的时间复杂度是 O(n)，其中 n 是字符串 s 的长度。具体分析如下：
1. 初始化哈希表的时间复杂度 ...
while嵌套在for里面，那时间复杂度不应该是n平方吗 O(n2)。
页:
[1]