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

Question

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

循环将扫描每个字符，如果遇到数字，它将计算数字的长度，并将指针增加该距离。因此，当指针p指向2并读取一个整数时，它会将sscanf数字 ( 201) 递增p3。两个嵌套循环，其中一个运行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)。