时间戳

首页 > 解决方案 > 使用数组和向量之间的时间复杂度差异

c++ - 使用数组和向量之间的时间复杂度差异

问题描述

对于查找第 n 个丑数（其素因数分解仅包含 2,3,5 ）（包括 1）的问题。当我使用以下使用向量的解决方案时，所花费的时间是 >1.013，这显示了 TLE，但是当我使用数组时，所花费的时间是0.9 被接受了！谁能解释为什么会这样？

#include <bits/stdc++.h>
using namespace std;
#define llb long long int
int main() {
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        llb ugly[n]; // To store ugly numbers 
        llb i2 = 0, i3 = 0, i5 = 0; 
        llb next_multiple_of_2 = 2; 
        llb next_multiple_of_3 = 3; 
        llb next_multiple_of_5 = 5; 
        llb next_ugly_no = 1; 
      
        ugly[0] = 1; 
        for (int i=1; i<n; i++) 
        { 
           next_ugly_no = min(next_multiple_of_2, 
                               min(next_multiple_of_3, 
                                   next_multiple_of_5)); 
           ugly[i] = next_ugly_no; 
           if (next_ugly_no == next_multiple_of_2) 
           { 
               i2 = i2+1; 
               next_multiple_of_2 = ugly[i2]*2; 
           } 
           if (next_ugly_no == next_multiple_of_3) 
           { 
               i3 = i3+1; 
               next_multiple_of_3 = ugly[i3]*3; 
           } 
           if (next_ugly_no == next_multiple_of_5) 
           { 
               i5 = i5+1; 
               next_multiple_of_5 = ugly[i5]*5; 
           } 
        } /*End of for loop (i=1; i<n; i++) */
        cout<<next_ugly_no<<endl;
    }
    return 0;
}

标签： c++

解决方案

如果您正确编写代码，性能应该几乎相同。

可能发生的事情（因为您没有显示另一种情况）是在std::vector您重新分配多次的情况下，可能是通过在每次外循环迭代时重新创建对象。如果您重新使用该对象，那么您应该会看到非常相似的性能。

边注：

llb ugly[n]; // To store ugly numbers

这是非标准 C++：可变长度数组 (VLA)。

推荐阅读