Big O表記の説明:空間と時間の複雑さ

あなたは本当にBigOを理解していますか?もしそうなら、これは面接の前にあなたの理解をリフレッシュします。そうでない場合でも、心配しないでください。コンピュータサイエンスのいくつかの取り組みに参加してください。

アルゴリズム関連のコースを受講したことがある場合は、BigO表記という用語を聞いたことがあると思います。まだ理解していない場合は、ここで説明し、実際の内容をより深く理解します。

Big O表記は、コンピューター科学者がアルゴリズムのコストを分析するための最も基本的なツールの1つです。ソフトウェアエンジニアにとっても、深く理解することをお勧めします。

この記事は、あなたがすでにいくつかのコードに取り組んでいることを前提に書かれています。また、一部の詳細な資料では、高校の数学の基礎も必要であるため、初心者にとっては少し快適ではない可能性があります。しかし、準備ができたら、始めましょう!

この記事では、BigO表記について詳しく説明します。理解を深めるために、アルゴリズムの例から始めます。次に、数学について少し説明して、正式に理解します。その後、BigO表記のいくつかの一般的なバリエーションについて説明します。最後に、実際のシナリオでBigOの制限のいくつかについて説明します。目次は以下にあります。

目次

  1. Big O表記とは何ですか、なぜそれが重要なのですか
  2. BigO表記の正式な定義
  3. ビッグO、リトルO、オメガ&シータ
  4. 典型的なBigO間の複雑さの比較
  5. 時間と空間の複雑さ
  6. 最高、平均、最悪、予想される複雑さ
  7. BigOが問題にならない理由
  8. 最終的には…

それでは始めましょう。

1. Big O表記とは何ですか、なぜそれが重要なのですか

「ビッグO表記は、引数が特定の値または無限大に向かう傾向がある場合の関数の制限動作を説明する数学表記です。これは、ポール・バッハマン、エドマンド・ランダウなどによって発明された一連の表記法のメンバーであり、まとめてバッハマン・ランダウ表記法または漸近表記法と呼ばれます。」—ウィキペディアによるビッグO表記法の定義

簡単に言うと、Big O表記は、代数的用語を使用してコードの複雑さを表します。

Big O表記とは何かを理解するために、典型的な例であるO(n²)を見てみましょう。これは通常「BigOsquared」と発音されます。ここでの文字「n」入力サイズを表し、「O()」内の関数「g(n)=n²」は、入力サイズに関してアルゴリズムがどれほど複雑であるかを示しています。

O(n²)の複雑さを持つ典型的なアルゴリズムは、選択ソートアルゴリズムです。選択ソートは、リストを反復処理して、インデックスiのすべての要素がリストのi番目に小さい/大きい要素であることを確認するソートアルゴリズムです。以下のCODEPENは、その視覚的な例を示しています。

アルゴリズムは次のコードで記述できます。i番目の要素がリスト内のi番目に小さい要素であることを確認するために、このアルゴリズムは最初にforループを使用してリストを反復処理します。次に、すべての要素について、別のforループを使用して、リストの残りの部分で最小の要素を見つけます。

SelectionSort(List) { for(i from 0 to List.Length) { SmallestElement = List[i] for(j from i to List.Length) { if(SmallestElement > List[j]) { SmallestElement = List[j] } } Swap(List[i], SmallestElement) } }

このシナリオでは、変数Listを入力と見なします。したがって、入力サイズnはList内の要素数です。ifステートメント、およびifステートメントによって制限される値の割り当てには一定の時間がかかると想定します。次に、ステートメントが実行された回数を分析することにより、SelectionSort関数の大きなO表記を見つけることができます。

まず、内側のforループがn回以内にステートメントを実行します。そして、iがインクリメントされた後、内側のforループはn-1回実行されます……1回実行されるまで、両方のforループが終了条件に達します。

これは実際には幾何学的な合計を与えることになり、高校の数学では、内側のループが1 + 2…+ n回繰り返されることがわかります。これは、n(n-1)/ 2回に相当します。これを掛けると、n²/ 2-n / 2になります。

大きなO表記を計算するときは、支配的な項のみを考慮し、係数は考慮しません。したがって、n²を最後の大きなOとします。これをO(n²)と記述します。これも「BigOsquared」と発音されます。

今、あなたは疑問に思うかもしれません、この「支配的な用語」はすべてについて何ですか?そして、なぜ係数を気にしないのですか?心配しないでください、私たちはそれらを一つずつ調べます。最初は理解するのが少し難しいかもしれませんが、次のセクションを読むと、すべてがはるかに理にかなっています。

2. BigO表記の正式な定義

昔々、彼の卓越性のために賢い人に報酬を与えたいと思っていたインドの王がいました。賢い人は、チェス盤を埋める小麦だけを求めました。

But here were his rules: in the first tile he wants 1 grain of wheat, then 2 on the second tile, then 4 on the next one…each tile on the chess board needed to be filled by double the amount of grains as the previous one. The naïve king agreed without hesitation, thinking it would be a trivial demand to fulfill, until he actually went on and tried it…

So how many grains of wheat does the king owe the wise man? We know that a chess board has 8 squares by 8 squares, which totals 64 tiles, so the final tile should have 2⁶⁴ grains of wheat. If you do a calculation online, you will end up getting 1.8446744*10¹⁹, that is about 18 followed by 18 zeroes. Assuming that each grain of wheat weights 0.01 grams, that gives us 184,467,440,737 tons of wheat. And 184 billion tons is quite a lot, isn’t it?

The numbers grow quite fast later for exponential growth don’t they? The same logic goes for computer algorithms. If the required efforts to accomplish a task grow exponentially with respect to the input size, it can end up becoming enormously large.

Now the square of 64 is 4096. If you add that number to 2⁶⁴, it will be lost outside the significant digits. This is why, when we look at the growth rate, we only care about the dominant terms. And since we want to analyze the growth with respect to the input size, the coefficients which only multiply the number rather than growing with the input size do not contain useful information.

Below is the formal definition of Big O:

The formal definition is useful when you need to perform a math proof. For example, the time complexity for selection sort can be defined by the function f(n) = n²/2-n/2 as we have discussed in the previous section.

If we allow our function g(n) to be n², we can find a constant c = 1, and a N₀ = 0, and so long as N > N₀, N² will always be greater than N²/2-N/2. We can easily prove this by subtracting N²/2 from both functions, then we can easily see N²/2 > -N/2 to be true when N > 0. Therefore, we can come up with the conclusion that f(n) = O(n²), in the other selection sort is “big O squared”.

You might have noticed a little trick here. That is, if you make g(n) grow supper fast, way faster than anything, O(g(n)) will always be great enough. For example, for any polynomial function, you can always be right by saying that they are O(2ⁿ) because 2ⁿ will eventually outgrow any polynomials.

Mathematically, you are right, but generally when we talk about Big O, we want to know the tight bound of the function. You will understand this more as you read through the next section.

But before we go, let’s test your understanding with the following question. The answer will be found in later sections so it won’t be a throw away.

質問:画像はピクセルの2D配列で表されます。ネストされたforループを使用してすべてのピクセルを反復する場合(つまり、すべての列を通過するforループがあり、次にすべての行を通過する内部の別のforループがある場合)、アルゴリズムの時間計算量はどのくらいですか?画像は入力と見なされますか?

3.ビッグO、リトルO、オメガ&シータ

大きなO:「f(n)はO(g(n))」一部の定数cおよびN₀の場合、すべてのN> N3オメガの場合はf(N)≤cg(N):「f(n)はΩ(g(g( n))」いくつかの定数cおよびN₀の場合、すべてのN>N₀シータの場合、f(N)≥cg(N):「f(n)はΘ(g(n))」、f(n)がO(g)の場合(n))およびf(n)はΩ(g(n))Little O:f(n)がO(g(n))およびf( n)はΘ(g(n))ではありません-Big O、Omega、Theta、LittleOの正式な定義

簡単に言えば:

  • Big O (O()) describes the upper bound of the complexity.
  • Omega (Ω()) describes the lower bound of the complexity.
  • Theta (Θ()) describes the exact bound of the complexity.
  • Little O (o()) describes the upper bound excluding the exact bound.

For example, the function g(n) = n² + 3n is O(n³), o(n⁴), Θ(n²) and Ω(n). But you would still be right if you say it is Ω(n²) or O(n²).

Generally, when we talk about Big O, what we actually meant is Theta. It is kind of meaningless when you give an upper bound that is way larger than the scope of the analysis. This would be similar to solving inequalities by putting ∞ on the larger side, which will almost always make you right.

But how do we determine which functions are more complex than others? In the next section you will be reading, we will learn that in detail.

4. Complexity Comparison Between Typical Big Os

When we are trying to figure out the Big O for a particular function g(n), we only care about the dominant term of the function. The dominant term is the term that grows the fastest.

For example, n² grows faster than n, so if we have something like g(n) = n² + 5n + 6, it will be big O(n²). If you have taken some calculus before, this is very similar to the shortcut of finding limits for fractional polynomials, where you only care about the dominant term for numerators and denominators in the end.

But which function grows faster than the others? There are actually quite a few rules.

1. O(1) has the least complexity

Often called “constant time”, if you can create an algorithm to solve the problem in O(1), you are probably at your best. In some scenarios, the complexity may go beyond O(1), then we can analyze them by finding its O(1/g(n)) counterpart. For example, O(1/n) is more complex than O(1/n²).

2. O(log(n)) is more complex than O(1), but less complex than polynomials

As complexity is often related to divide and conquer algorithms, O(log(n)) is generally a good complexity you can reach for sorting algorithms. O(log(n)) is less complex than O(√n), because the square root function can be considered a polynomial, where the exponent is 0.5.

3. Complexity of polynomials increases as the exponent increases

For example, O(n⁵) is more complex than O(n⁴). Due to the simplicity of it, we actually went over quite many examples of polynomials in the previous sections.

4. Exponentials have greater complexity than polynomials as long as the coefficients are positive multiples of n

O(2ⁿ) is more complex than O(n⁹⁹), but O(2ⁿ) is actually less complex than O(1). We generally take 2 as base for exponentials and logarithms because things tends to be binary in Computer Science, but exponents can be changed by changing the coefficients. If not specified, the base for logarithms is assumed to be 2.

5. Factorials have greater complexity than exponentials

If you are interested in the reasoning, look up the Gamma function, it is an analytic continuation of a factorial. A short proof is that both factorials and exponentials have the same number of multiplications, but the numbers that get multiplied grow for factorials, while remaining constant for exponentials.

6. Multiplying terms

When multiplying, the complexity will be greater than the original, but no more than the equivalence of multiplying something that is more complex. For example, O(n * log(n)) is more complex than O(n) but less complex than O(n²), because O(n²) = O(n * n) and n is more complex than log(n).

To test your understanding, try ranking the following functions from the most complex to the lease complex. The solutions with detailed explanations can be found in a later section as you read. Some of them are meant to be tricky and may require some deeper understanding of math. As you get to the solution, you will understand them more.

質問:次の機能を最も複雑なものからリースの複雑なものまでランク付けします。セクション2の質問の解決策:実際には、理解度をテストするためのトリック質問であることが意図されていました。ネストされたforループがあるため、質問はO(n²)に答えさせようとします。ただし、nは入力サイズであると想定されています。画像配列が入力であり、すべてのピクセルが1回だけ繰り返されたため、答えは実際にはO(n)です。次のセクションでは、このような例について詳しく説明します。

5.時間と空間の複雑さ

So far, we have only been discussing the time complexity of the algorithms. That is, we only care about how much time it takes for the program to complete the task. What also matters is the space the program takes to complete the task. The space complexity is related to how much memory the program will use, and therefore is also an important factor to analyze.

The space complexity works similarly to time complexity. For example, selection sort has a space complexity of O(1), because it only stores one minimum value and its index for comparison, the maximum space used does not increase with the input size.

Some algorithms, such as bucket sort, have a space complexity of O(n), but are able to chop down the time complexity to O(1). Bucket sort sorts the array by creating a sorted list of all the possible elements in the array, then increments the count whenever the element is encountered. In the end the sorted array will be the sorted list elements repeated by their counts.

6. Best, Average, Worst, Expected Complexity

The complexity can also be analyzed as best case, worst case, average case and expected case.

Let’s take insertion sort, for example. Insertion sort iterates through all the elements in the list. If the element is larger than its previous element, it inserts the element backwards until it is larger than the previous element.

If the array is initially sorted, no swap will be made. The algorithm will just iterate through the array once, which results a time complexity of O(n). Therefore, we would say that the best-case time complexity of insertion sort is O(n). A complexity of O(n) is also often called linear complexity.

Sometimes an algorithm just has bad luck. Quick sort, for example, will have to go through the list in O(n) time if the elements are sorted in the opposite order, but on average it sorts the array in O(n * log(n)) time. Generally, when we evaluate time complexity of an algorithm, we look at their worst-case performance. More on that and quick sort will be discussed in the next section as you read.

The average case complexity describes the expected performance of the algorithm. Sometimes involves calculating the probability of each scenarios. It can get complicated to go into the details and therefore not discussed in this article. Below is a cheat-sheet on the time and space complexity of typical algorithms.

Solution to Section 4 Question:

By inspecting the functions, we should be able to immediately rank the following polynomials from most complex to lease complex with rule 3. Where the square root of n is just n to the power of 0.5.

Then by applying rules 2 and 6, we will get the following. Base 3 log can be converted to base 2 with log base conversions. Base 3 log still grows a little bit slower then base 2 logs, and therefore gets ranked after.

The rest may look a little bit tricky, but let’s try to unveil their true faces and see where we can put them.

First of all, 2 to the power of 2 to the power of n is greater than 2 to the power of n, and the +1 spices it up even more.

And then since we know 2 to the power of log(n) with based 2 is equal to n, we can convert the following. The log with 0.001 as exponent grows a little bit more than constants, but less than almost anything else.

The one with n to the power of log(log(n)) is actually a variation of the quasi-polynomial, which is greater than polynomial but less than exponential. Since log(n) grows slower than n, the complexity of it is a bit less. The one with the inverse log converges to constant, as 1/log(n) diverges to infinity.

階乗は乗算で表すことができるため、対数関数の外で加算に変換できます。「nchoose2」は、3次項が最大の多項式に変換できます。

そして最後に、関数を最も複雑なものから最も複雑でないものへとランク付けできます。

BigOが重要でない理由

!!! —警告— !!! ここで説明する内容は、一般に、世界中のほとんどのプログラマーに受け入れられいません。面接では自己責任で話し合ってください。人々は実際に、ここのように当局に質問したためにGoogleのインタビューに失敗した方法についてブログに書いています。!!! —警告— !!!

Since we have previously learned that the worst case time complexity for quick sort is O(n²), but O(n * log(n)) for merge sort, merge sort should be faster — right? Well you probably have guessed that the answer is false. The algorithms are just wired up in a way that makes quick sort the “quick sort”.

To demonstrate, check out this trinket.io I made. It compares the time for quick sort and merge sort. I have only managed to test it on arrays with a length up to 10000, but as you can see so far, the time for merge sort grows faster than quick sort. Despite quick sort having a worse case complexity of O(n²), the likelihood of that is really low. When it comes to the increase in speed quick sort has over merge sort bounded by the O(n * log(n)) complexity, quick sort ends up with a better performance in average.

I have also made the below graph to compare the ratio between the time they take, as it is hard to see them at lower values. And as you can see, the percentage time taken for quick sort is in a descending order.

The moral of the story is, Big O notation is only a mathematical analysis to provide a reference on the resources consumed by the algorithm. Practically, the results may be different. But it is generally a good practice trying to chop down the complexity of our algorithms, until we run into a case where we know what we are doing.

In the end…

I like coding, learning new things and sharing them with the community. If there is anything in which you are particularly interested, please let me know. I generally write on web design, software architecture, mathematics and data science. You can find some great articles I have written before if you are interested in any of the topics above.

Hope you have a great time learning computer science!!!