c - 两个循环的时间复杂度

Question

我有两个用 C 编写的循环，第一个循环运行 n 次，其中 n 是输入字符串的长度。假设输入字符串为:*& 201 +ACD 3491 AASD 3。

循环将扫描每个字符，如果遇到数字，它将计算该数字的长度，并将指针增加该距离。因此，当指针p指向2并读取一个整数时，它将sscanf数字(201)并将 p 增加 3。两个嵌套循环，其中一个运行 N 次，另一个运行 M 次，其时间复杂度为 O( N * M)。

可以肯定地说，我的算法中的时间复杂度也是O(N * M)，其中M是在该特定位置扫描的位数迭代？如果不是，整个事情的时间复杂度是多少？

编辑:

这是一些代码

char c;
while ((c = fgets(fp)) != EOF) {
    // scans characters, if a digit is encountered, get digit_length
    for (int i = 0; i < digit_length; i++)
        p++;
}

Answer 1

如果您正在扫描以下所有号码:

201
01
1
3491
491
91
1
3

那么时间将是(最坏情况)O(N^2)。如果你以某种方式避免这种情况(你应该这样做)，那么它将是 O(N)。