运行时间

如果写出了一个时间复杂度为O(n)的算法,那么可以估算出N为多大的时候,算法的执行时间会超过一秒,如果知道n的规模已经足够让时间复杂度为O(n)的算法时间超过一秒,那么就要考虑时间复杂度为O(logn)的算法了

---

我们可以通过程序测试计算机1s大概可以处理多大量级的数据

/**
 * ClassName: ${NAME}
 * package: ${PACKAGE_NAME}
 * Description:
 * @Author: innno
 * @Create: 2024/2/27 - 21:54
 * @Version: v1.0
 */
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

void function1(ll n)//O(n)
    {
        ll k = 0;
        for (ll i = 0; i < n; i++)
            {
                k++;
            }
    }

void function2(ll n)//O(n^2)
    {
        ll k = 0;
        for (ll i = 0; i < n; i++)
            {
                for (ll j = 0; j < n; j++)
                    {
                        k++;
                    }
            }
    }

void function3(ll n)//O(nlogn)
    {
        ll k = 0;
        for (ll i = 1; i < n; i++)
            {
                for (ll j = 1; j < n; j *= 2)
                    {
                        k++;
                    }
            }
    }

int main()
    {
        ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
        ll n;
        cin >> n;
        std::chrono::milliseconds start_time = duration_cast<std::chrono::milliseconds>(
                std::chrono::system_clock::now().time_since_epoch());
        //function1(n);
        //function2(n);
        //function3(n);
        std::chrono::milliseconds end_time = duration_cast<std::chrono::milliseconds>(
                std::chrono::system_clock::now().time_since_epoch());
        cout << "function: " << end_time.count() - start_time.count() << "ms" << endl;

        return 0;
    }

测试结果为:

O(n)约为1*10^9为1s

O(n^2)约为4.5*10^4为1s

O(nlogn)约为1.7*10^7为1s