提问关于时间复杂度计算

Question

算法分析题，阅读以下代码：

int a[100];

Fun(int a[], int n)

{

for(int i=1; i<=n; ++i)

{

    cin>>a[i];

}

int K=1;

for(int i=1; i<=n; ++i)

{

    if(i > 1 && a[i] < a[i - 1])

    K = i;

    while (K < n && a[i] >= a[K +1])

        ++ K;

    cout<< K;

}

}

若输入的a数组是一个严格单调递增的数列，分析此程序的时间复杂度。

Answer 1

第一个for循环是O(N)
由于a数组是严格单调递增，第二个循环里的if条件不成立，故每次i循环时K不会被重置，while循环当i=1时，条件不成立，当i>=2时，++K只执行一次，因此第二个for循环的时间复杂度也是O(N)
最终整个函数的时间复杂度时O(N)