Overview

This article is a translation of O（オーダー）記法とアルゴリズムの計算量の求め方
.
We will summarize the prerequisite knowledge about the O notation that roughly calculates the calculation performance of the algorithm and how to calculate the amount of calculation.

What is the amount of calculation (order)?

An index that expresses the calculation performance of the algorithm as the ratio of how much the execution time increases to the increase in the amount of data.

• Time complexity
  • processing time
• Spatial complexity
  • memory usage

Big O/Big θ/Big Ω

Each describes the calculation time, but summarizes the differences in academic meaning.

• Big O
  • Upper limit of calculation time
• Big θ
  • Lower limit of calculation time
• Big Ω
  • Both O and Ω

Best/Worst/Expected Case

We will summarize the three patterns that represent the execution time of the algorithm.

• Best case
  • Lower limit of computational complexity. The case where the values ​​of all elements are equal. There is not much discussion because the value is far from the worst case and the expected case, and it is usually the case that can be executed with O (₁).
• Worst case
  • Upper limit of computational complexity.
• Expected (average) case
  • Average amount of calculation. The case where the value of the element is average.

For many algorithms, the worst case and the expected case are often the same. It was

O notation

The representative ones are summarized in the order of the shortest processing time.

How to calculate the amount of calculation

Calculate the number of steps and calculate the amount of calculation based on the total.
The following two points are of low importance when calculating the amount of calculation, so they are omitted.

• Omit other than the maximum degree term
  • O (n² + n)
  • O (n²)
• Omit the coefficient
  • O (2n)
  • O (n)

Whether to add or multiply the processing execution time in the step calculation depends on whether each processing occurs at the same time or not.

If it does not happen at the same time, add the execution time.

for (condition) {
  // do something
}

for (condition) {
  // do something
}

If it happens at the same time, it takes time to execute.

for (condition) {
  for (condition) {
    // do something
  }
}

example

Linear search

const targetData = 4; // Run once
const data = [1, 2, 3, 4, 5]; // Run once

for (let i = 0; i <data.length; i ++) {
if (targetData == data [i]) {
  console.log (`$ {i} th found data`); // data.length executed times → executed n times
    return;
  }
}

console.log ('No desired data'); // Run once

In the case of the above code, the total number of steps is 1 + 1 + n + 1 = 3n.
Since the coefficient is excluded, the amount of calculation is O (n).

for statement dual structure

const data = [1, 2, 3, 4, 5]; // Run once

for (let i = 0; i <data.length; i ++) {
console.log (`$ {i} th process`); // Executed once
for (let j = 0; j <data.length; j ++) {
console.log (j); // 4 * Executed 4 times → Executed n² times
  }
}

In the above case, the number of steps is 1 + 1 + n² = 2n², so the amount of calculation is O (n²) excluding the coefficient.

Algorithms whose computational complexity is logarithmic

const n = 10; // executed once

for (let i = 0; i <n; i = i * 2) {
  console.log (i ++); // log2 ⁿ Executed times
}

When n is 1
Number of loops 1

When n is 4
Number of loops 2

When n is 8
Number of loops 3

The number of loops is calculated by log2ⁿ.
Since the number of steps is 1 + log2ⁿ, the amount of calculation is log n, omitting various things.

Reference link

• 計算量オーダーについて
• [初心者向け] プログラムの計算量を求める方法
• [初心者向け] プログラムの計算量を求める方法
• 計算量オーダーの求め方を総整理！ 〜 どこから log が出て来るか 〜
• techscore - 開発新卒に捧ぐ、基本のアルゴリズムと計算量

Reference books

• 世界で闘うプログラミング力を鍛える本 ~コーディング面接189問とその解法~
• アルゴリズム図鑑 絵で見てわかる26のアルゴリズム
• プログラミングコンテスト攻略のためのアルゴリズムとデータ構造
• アルゴリズムを、はじめよう
• Web+DB press vol.91 2016