时间复杂度

  • 时间复杂度是衡 量算法执行时间随着输入规模增长的增长率。
  • 通过分析算法中基本操作的执行次数来确定时间复杂度。
  • 常见的时间复杂度
    • 常数时间 O(1)
    • 线性时间 O(n)
    • 对数时间 O(log n)
    • 平方时间 O(n^2)
  • 计算的时候，关注点是复杂度的数量级，并不要求严格的表达式

一般情况下，关注的是最坏时间复杂度，用O(f(n))来表示，大多数情况下仅需要估算即可。

一般情况下，评测机一秒可以跑2e8次运算，所以要尽可能地让程序运算规模数量控制在1e8以内。
举个例子：n = 1e4 O(n^2) = 1e8

空间复杂度

  • 空间复杂度是衡量算法执行过程中所需的存储空间随输入规模增长的增长率
  • 通过分析算法中所使用的额外存储空间的大小来确定空间复杂度
  • 常见的空间复杂度
    • 常数空间 O(1)
    • 线性空间 O(n)
    • 对数空间 O(log n)
    • 平方空间 O(n^2)

一般情况下，关注的是最坏空间复杂度，用O(f(n))来表示，大多数时候程序占用的空间一般可以根据开的数组大小精确算出，但也存在需要估算的情况。题目一般不会卡空间，一般是卡时间。

举个例子，假设题目限制128MB，1int\~32bit\~4Bytes，128MB\~3e7int

分析技巧

  1. 理解基本操作： 基本操作可以是算术运算（加法、乘法、位运算等等）、比较操作、赋值操作等。一般称之为原子操作（时间复杂度O(1)）。
  2. 关注循环结构：循环是算法中常见的结构，它的执行次数对于时间复杂度的分析至关重要。
    举个例子，for()执行n次，则时间复杂度为O(n)，如果里面再嵌套一个for则时间复杂度为O(n^2)。
  3. 递归算法：递归算法的时间和空间复杂度分析相对复杂。需要确定递归的深度以及每个递归调用的时间和空间的开销。
    可以绘制递归树。
  4. 最快情况分析：对于时间复杂度的分析，通常考虑最坏情况下的执行时间。需要考虑输入数据使得算法时间达到最大值的情况。
  5. 善用结论：某些常见算法的时间和空间复杂度已经被广泛研究与证明。可以利用这些已知结果来分析算法的复杂度。
#include <iostream>
#include <vector>
using namespace std;

int calculateSum(vector<int>& nums)
{
    int sum = 0;
    for (int num : nums)
    {
        sum += num;
    }
    return sum;
}

int main()
{
    int n;
    cout << "Enter the number of elements: ";
    cin >> n;

    vector<int> nums(n);
    cout << "Enter the elements: ";
    for (int i = 0; i < n; i++)
    {
        cin >> nums[i];
    }
    int sum = calculateSum(nums);
    cout << "Sum of the elements: " << sum << endl;

    return 0;
}

时间复杂度O(n)
该算法通过循环遍历数组中的每个元素，并对它们求和，因此时间复杂度与数组中的元素数量成正比。

空间复杂度O(n)
算法使用了一个大小为n的向量来存储输入元素，所以空间复杂度与输入元素的数量成正比。

渐进符号*

渐进符号是函数的阶的规范描述。简单来说，渐进符号忽略了一个函数中增长较慢的部分以及各项的系数（在时间复杂度相关分析中，系数一般被称作「常数」），而保留了可以用来表明该函数增长趋势的重要部分。
\Theta定义了一种精确的渐近行为（exact asymptotic behavior）