我有两个用 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++;
}
最佳答案
如果您正在扫描以下所有号码:
201
01
1
3491
491
91
1
3
那么时间将是(最坏情况)O(N^2)。如果你以某种方式避免这种情况(你应该这样做),那么它将是 O(N)。
关于c - 两个循环的时间复杂度,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/11727288/