c++ - 时间复杂度 - 大 O - 显示不在文件中的间隔中的数字

Question

我想知道这段代码的时间复杂度(big-O):

(它读取一个文本文件如下: 第一行是一个数字 n，第二行是一个升序数字列表 - 最大值。 n 个数字 - 它显示了从 1 到 n 的所有数字，这些数字不在文本文件中)

#include <iostream>
#include <fstream>
using namespace std;

int interval(int a, int b, int &ok) { 
    for(int i=1; i<(b-a); i++) {
      cout << a+i << " "; ok=1;
    }
}

int main()
{
    int n=0, ok=0, a=0, b=0; 
    ifstream fisier("numere.in");
    fisier >> n;
    while(fisier >> b) { b
        interval(a,b,ok); 
        a = b;
    } interval(b,n+1,ok);
    if(ok == 0) cout << "Nu exista";
    return 0;
}

我认为它是 n*logn 但我不确定。谢谢

Answer 1

如果数字是 a1,a2,a3...a(n) 那么，

首先它进行 a1 次，然后在下一次迭代中进行 a2-a1 次，在下一次迭代中进行 a3-a2 次 .... a(n) - a(n-1) 次。将其相加得到 a(n) 次，即 O(n)。