小编Van*_*ika的帖子

以下代码的时间复杂度应该是多少？我试图思考并提出 O(n ² ) 但输出说它是 O(n)。有人可以通过代码解释吗？

for(int i = 0; i < n; i++){
    for(; i < n; i++){
        cout << i << endl;
    }
}

根据我的说法，时间复杂度应该是 O(nlogn)，因为外循环工作直到 n/2^k =1 并且内循环工作 n 次。谁能告诉我是否正确。

 while(n){ 
  j=n; 
  while(j>1){ 
    j-=1; 
  } 
  n/=2; 
} 

有N个楼梯，站在底部的人想要到达顶部。该人一次可以爬 1 个楼梯或 2 个楼梯。数数方式，此人可登顶（顺序无所谓）。注意：顺序无关紧要意味着对于 n=4 {1 2 1},{2 1 1},{1 1 2} 被认为是相同的。

https://practice.geeksforgeeks.org/problems/count-ways-to-nth-stairorder-does-not-matter/0

所以我一直在尝试解决这个问题，我面临的问题是我不明白我们如何解决这些顺序无关紧要的问题？当订单很重要时，我能够解决这个问题，但我无法开发解决这个问题的逻辑。

这是我在订单重要时编写的代码

long int countWaysToStair(long int N)
{
    if(N == 1 || N == 2)
    return N;

    long int dp[N+1];

    dp[0] = 1;
    dp[1] = 1;

    dp[2] = 2;

    for(int i=3;i<=N;i++)
    {
      dp[i] = dp[i-1] + dp[i-2];
    } 
    return dp[N];
}

输入：4 预期输出：3 我的输出：5