[已解决]问时间复杂度

ynnh

请问这段代码的时间复杂度是多少
int lengthOfLongestSubstring(char * s){
    int hash[128] = {0};    // 模拟哈希表
    int max = 0;    // 最大值
    for(int i = 0, j = 0; i < strlen(s); i++){
        hash[s[i]]++;
        while(hash[s[i]] > 1) hash[s[j++]]--;
        max = max < (i-j+1)?(i-j+1):max;
    }
    return max;
}

最佳答案

月排行榜 / 总排行榜

isdkz

2023-9-21 16:51:00

这段代码的时间复杂度是 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

这段代码的时间复杂度是 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)。

ynnh

isdkz 发表于 2023-9-21 16:51
这段代码的时间复杂度是 O(n)，其中 n 是字符串 s 的长度。具体分析如下：

1. 初始化哈希表的时间复杂度 ...

while嵌套在for里面，那时间复杂度不应该是n平方吗

sfqxx

O(n²)。