← 返回题目列表

AtCoder · APG4b_w

W. 2.06.计算量

中文机器翻译题面 查看原题
page_url:https://atcoder.jp/contests/apg4b/tasks/APG4b_w 任务ID:3769

上一页 | 下一页

要点

  • 运行程序时,执行时间取决于处理内容。
  • 计算机的存储区域(内存)是有限的,程序中使用的变量数量会消耗内存。
  • 估计程序执行时间和内存使用量将如何根据输入而变化。時間計算量、空間計算量这就是所谓的
  • 表达计算量:订单符号 经常使用经常被使用

算法

当创建执行某种处理的程序时,计算过程是执行什么样的计算。 它被称为算法。
例如,考虑一个计算从 1 到 100 的数字总和的程序。 一种算法是按顺序添加 1+2+3+...+99+100。我们称这个算法为A。 另一方面, 使用公式\frac{100 \cdot (1 + 100)}{2}计算也是一种算法。我们称这个算法为B。

如本例所示,创建程序时可以考虑多种算法。 在这种情况下,您必须选择使用哪种算法。

计算机执行一次计算需要花费少量时间,因此执行的计算越多,执行时间就越长。 通过选择需要较少计算的算法,您可以创建运行速度更快的程序。

在上面的例子中,算法A需要99次加法,但算法B总共需要3次计算才能得到结果:加、乘、除。 您可以根据所需的计算次数来大致估算性能,例如算法A需要99次计算,算法B需要3次计算。

比较算法性能的方法有很多种,但作为一个指标 有一个概念叫做計算量。

计算时间和存储空间

如上所述,当计算机执行程序时,根据处理内容需要时间。

计算机的存储区域称为内存。内存是有限的,每个使用的变量都会消耗内存。 字符串和数组变量消耗内存取决于内部元素的数量。 例如,int类型N元素数组是 它消耗与使用Nint 变量相同的内存量。 长度也一样 字符串N是 它消耗与使用Nchar 变量相同的内存量。

計算量

程序对输入执行必要的计算并输出结果。 显示此时所需计算时间和所需存储空间量根据输入而变化的指标。計算量。

计算量为 有時間計算量和空間計算量。当我们简单地提到计算量时,我们通常指的是所需的时间量。

時間計算量

执行程序所需的计算步骤数如何随输入变化的指示器。 它被称为時間計算量。 计算步骤的数量是算术运算、数值比较等的数量。

空間計算量

指示运行程序所需的内存量如何响应输入而变化。空間計算量。

计算复杂度示例

以下程序是 总计1到N( 计算1+2+3+ \cdots +N)。

#include <bits/stdc++.h>
using namespace std;

int main() {
  int N;
  cin >> N;
  int sum = 0;
  for (int i = 1; i <= N; i++) {
    sum += i;
  }
  cout << sum << endl;
}

在此程序中,for 语句 由于该过程重复N次,因此计算步骤数为 它根据N而变化。 由于重复 N次,计算步骤数约为N次。 这种情况下的时间复杂度可以使用下面介绍的顺序符号来计算。 表示为O(N)。

该程序中使用的变量是输入 无论N不管int N和int sum和int i有三个。 这种情况下的空间复杂度是使用顺序符号计算的。O(1)。

订单符号 经常使用

确切的计算步骤数和所需的存储空间量将根据用于实现的编程语言和实现方法而变化。 计算量很难准确估计。

因此,作为时间复杂度和空间复杂度的表达, 经常使用订单符号 经常使用 O(\cdot)。

例如, 在顺序表示法中,表达式3 N^2 + 7N + 4为 表示为O(N ^ 2)。

您可以按照以下步骤获取顺序符号。

可以在一般表达式中使用系数吗?
  • 步骤 1:省略系数。但是,常量设置为 1。
  • 第 2 步: 提取当N增加时影响最大的项,并且 写入O(項)。 对于表达式

    補足:N^2 + N + 1,“N^2」「N」「1”每个項。

“影响最大的术语”是N增加时,将其视为“增加最快的项”。 例如 如果你比较N和N^2,它将如下表所示,所以3N^2可以说影响较大。 以顺序表示法表达表达式

N N^2
N=1 1 1
N=10 10 100
N=100 100 10,000
N=1,000 1,000 1,000,000

3 N^2 + 7N + 4的步骤如下。

  • 步骤 1:省略系数N^2 + N + 1。
  • 第 2 步: 提取当N^2 + N + 1中影响最大的术语是N^2所以O(N^2)。

同样2N + 10如果O(N)。

例題

请用顺序符号表达以下各表达式。

  1. N + 100
  2. 10N + N^3
  3. 3 + 5
  4. 2^N + N^2

    補足:2^N = \underbrace{2 \times 2 \times \cdots \times 2}_{N個}

回答

点击打开答案

  1. O(N)
  2. O(N^3)
  3. O(1)
  4. O(2^N)

2^N和N^2的比较如下表所示。

2^N N^2
N=1 2 1
N=10 1,024 100
N=30 1,073,741,824 = 約10億 900

计算金额如何计算(顺序表示法)

计算计算量,需要用公式来表达计算步数。

下面的程序没有意义,但是我们考虑一下计算复杂度。

#include <bits/stdc++.h>
using namespace std;

int main() {
  int N;
  cin >> N;

  int sum = 0;

  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
      sum += i * j;
    }
  }

  for (int i = 0; i < N; i++) {
    sum += i;
  }

  for (int i = 0; i < N; i++) {
    sum *= i;
  }

  cout << sum << endl;
}

有1个双循环和2个单循环,所以计算步数为 它将是关于N^2 + 2N。 用顺序符号来表达是O(N^2)。 因此,该程序的时间复杂度为O(N^2)。

这样, 如果是简单的算法,就不需要找到精确的公式。 “因为有一个过程重复了N次,O(N)”或“有一个从 0 到 N 旋转的双循环。O(N^2)等可以估计。


例

下面是一些计算命令的具体程序示例。

O(1)

以下程序是 它使用公式计算1到N的总和。 该程序的计算复杂度为O(1)。

#include <bits/stdc++.h>
using namespace std;

int main() {
  int N;
  cin >> N;
  int sum = N * (N + 1) / 2;
  cout << sum << endl;
}
入力
10
実行結果
55

O(N)

以下程序的元素数量 它计算N数组中包含的偶数的数量。 该程序的计算复杂度为O(N)。

#include <bits/stdc++.h>
using namespace std;

int main() {
  int N;
  cin >> N;
  vector<int> a(N);
  for (int i = 0; i < N; i++) {
    cin >> a.at(i);
  }

  int cnt = 0;
  for (int i = 0; i < N; i++) {
    if (a.at(i) % 2 == 0) {
      cnt++;
    }
  }
  cout << cnt << endl;
}
入力
5
1 4 2 5 9
実行結果
2

O(N ^ 2)

以下程序基于乘法表。N×N这就是填充方块的内容。 该程序的计算复杂度为O(N^2)。

#include <bits/stdc++.h>
using namespace std;

int main() {
  int N;
  cin >> N;

  vector<vector<int>> table(N, vector<int>(N));
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
      table.at(i).at(j) = (i + 1) * (j + 1);  // N×N回実行される
    }
  }

  // 出力
  for (int i = 0; i < N; i++) {
    for (int j = 0; j < N; j++) {
      cout << table.at(i).at(j);
      if (j != N - 1) {
        cout << " ";
      }
      else {
        cout << endl;
      }
    }
  }
}
入力
9
実行結果
1 2 3 4 5 6 7 8 9
2 4 6 8 10 12 14 16 18
3 6 9 12 15 18 21 24 27
4 8 12 16 20 24 28 32 36
5 10 15 20 25 30 35 40 45
6 12 18 24 30 36 42 48 54
7 14 21 28 35 42 49 56 63
8 16 24 32 40 48 56 64 72
9 18 27 36 45 54 63 72 81

N \times N由于使用了元素的二维数组,因此空间计算量也减少了。O(N^2)。

O(\log N)

易于上手\log已解释。 表达式

\log_x N是x的威力有多大?N。 例如,2^4 = 16所以,\log_2 16 = 4。

看下图。如果将一根长度为 8 的棍子反复切成两半(除以 2),直到长度变为 1,那么它会被切成多少次?\log_2 8次。

在计算金额中出现是这样的\log通常表示“减半的次数”。 由于与

\log N为N相比非常小,因此计算量为 即使出现O(\log N),它通常也不会影响执行时间那么多。 如果想知道具体值,可以通过Google搜索“log_2值”找到。

注:具体定义属于高中数学范畴,想了解更多的同学请单独研究。
另外,在顺序表示法中,对数的底数经常被省略。在这种情况下,请考虑省略 2。
实际上,log底数的差异可以看成只是常数次的差异,因此在省略系数的顺序表示法中将其省略。 它计算

以下程序是 总计N除以 2 的次数。 该程序的计算复杂度为O(\log N)。

由于程序执行与上图相同的处理,因此循环次数约为 可以看到会是\log_2 N次。

#include <bits/stdc++.h>
using namespace std;

int main() {
  int N;
  cin >> N;
  int cnt = 0;
  while (N > 1) {
    cnt++;
    N /= 2;
  }
  cout << cnt << endl;
}

大概计算量

主要计算量大致大小如下。

O(1) < O(log N) < O(N) < O(N log N) < O(N ^ 2) < O(2 ^ N)

如果时间复杂度为O(1)边可以更快地计算, 越靠近O(2^N)一侧,需要的时间越长。

这些关系如下图所示。 下表为

入力N与执行时间的对应关系。

N O(1) O(\log N) O(N) O(N \log N) O(N^2) O(2^N)
1 一瞬 一瞬 一瞬 一瞬 一瞬 一瞬
10 一瞬 一瞬 一瞬 一瞬 一瞬 一瞬
1000 一瞬 一瞬 一瞬 一瞬 约0.01秒 地球爆発
10^6 一瞬 一瞬 约0.01秒 约0.2秒 约3小时 地球爆発
10^8 一瞬 一瞬 约1秒 约30秒 约3年 地球爆発
10^{16} 一瞬 一瞬 约3年 约170年 地球爆発 地球爆発

当尝试创建一个在大约 1 秒内完成计算的程序时, 在估算出输入大小的上限后,需要选择计算量能够在1秒内完成的算法。 如果您想创建一个程序,在 1 秒内完成计算,输入最多为

例如, 在顺序表示法中,表达式N=10^6, O(N^2)的算法不够,所以 它必须使用O(N)算法来实现。

对于 AtCoder 问题,执行时间约束通常在 2 秒左右。 参加比赛的人将能够 请记住,大约可以计算10^8次。

有多个输入时的顺序表示法

即使程序有多个输入,也可以使用顺序符号来表示计算量。 在这种情况下,保留每个变量并写入它。 例如,两个输入 如果您想接收N和M像O(N + M), O(NM), O((N + M) \log N)一样写。 当计算步数为

N^2 M + NM + NM^2时,只留下影响最大的项。O(N^2M + NM^2)。

即使你不知道该留哪一项,只要能比较计算量就没有问题。请记住,多个输入可能会影响计算量。


详情

顺序表示法的陷阱

用顺序表示法表达计算量可以更容易进行比较,但必须注意顺序表示法只允许粗略比较。

在顺序表示法中,仅保留影响最大的项,并省略系数。 例如,这减少了计算步骤的数量。 变成20N的算法 当尝试比较导致2N的算法时, 实际上,相差10倍,但从顺序上看,两者都是 将显示O(N)。

出于同样的原因,O(N)的算法 A 和 比较O(N \log N)的算法B时, 尽管算法A在计算复杂度上更快,但在实际操作中可能会出现算法B更快的情况。

如果你想要准确的比较,你需要实际测量时间并进行比较。

STL函数复杂性

1.14 STL 函数中引入的函数的计算复杂度如下。

STL 函数 计算量(数组元素数N)
排序 O(N \log N)
反向 O(N)

以下程序对输入数组进行排序并输出。

#include <bits/stdc++.h>
using namespace std;

int main() {
  int N;
  cin >> N;
  vector<int> A(N);

  // O(N)
  for (int i = 0; i < N; i++) {
    cin >> A.at(i);
  }

  // O(N log N)
  sort(A.begin(), A.end());

  // O(N)
  for (int i = 0; i < N; i++) {
    cout << A.at(i) << endl;
  }
}

有两次循环N次,所以总计算量为 好像是O(N), sort函数的计算复杂度为O(N \log N)循环部分O(N),所以整个程序的计算复杂度是O(N \log N)。

日志的属性

  • O(\log 5N) → O(\log N) 对数中的系数被省略。

  • O(\log NM) → O(\log N + \log M) 你可以用任何一种方式写,但是在考虑大小时,如果你知道这种关系,可能会更容易估计。

  • O(\log N^2) → O(\log N)

  • O(\log 2^N) → O(N)


演習問題

请解决链接目的地的问题。