コーディングテストにおけるコードのTIMEOUT ERRORについて


オンラインでコーディングテスト練習ができるCodilityのMaxProductOfThreeという問題のコードですが、テストケースが全て正解でもDetected
time complexityが`O(N**3)`だったので、テストスコアが44%/100%と表示されました。

[（参考）MaxProductOfThreeについて日本語で書かれた記事](http://codility-lessons-
jp.blogspot.com/2014/07/lesson-4-maxproductofthree.html)

参考記事で書かれている`O(N)`のコードはわかりにくいと感じてしまうのですが、実際にJobHuntingなどで課されるコーディングテストではコードの可読性とtime
complexityのどちらを優先させるべきなのでしょうか。

また、近年ではPCのスペックやクラウドのメモリなども増えましたが、それでもやはりできるだけtime
complexityを考えてコードを書くエンジニアの方が良いのでしょうか。

実際に書いた`O(N**3)`のコード

[code]

    def solution(A):
        for i in range(0, len(A)-1):
            for j in range(len(A)-1, i, -1):
                if A[j] < A[j-1]:
                    A[j-1], A[j] = A[j], A[j-1]
    
    
        check1 = A[len(A)-1] * A[len(A)-2] * A[len(A)-3]
        check2 = A[len(A)-1] * A[0] * A[1]
    
        print(A)
    
        if check1 > check2:
            return check1
        else:
            return check2
    
[/code]




部分的な回答：時間計算量を考えることは重要です。

[ムーアの法則](https://ja.wikipedia.org/wiki/%E3%83%A0%E3%83%BC%E3%82%A2%E3%81%AE%E6%B3%95%E5%89%87)を信じるのであればコンピューターの計算速度は指数的に増加していくわけですが、それでも多項式の次数レベルの時間計算量の差は大事です。現実的には目の前の問題をすぐ解いて欲しいわけで、コンピューターの計算速度が充分大きくなってくれるのを待つのでは現状まだ間に合いません。

特に問題となってくるのは、入力の数が多い場合です。手元の Python 環境(※)で試してみたところ、次の単純な O(N) のループでは、`N = 10
** 8` のとき実行におおよそ 1 秒かかりました。

[code]

    def repeat(n):
        for i in range(n):
            pass
    
[/code]

(※) 手元の環境：Core i7-8700, Python 3.7, Jupyter Notebook

このことから概算するに、同じ環境で同じ `N = 10 ** 8` を処理するとき、時間計算量によって次のように実行時間が変わってきます。

[code]

    O(N)   1 秒
    O(N²)  10⁸ 秒 ≒ 1000 日 ≒ 3 年
    O(N³)  10¹⁶ 秒 ≒ 3 億年
    
[/code]

数年待てば「実行に 1 秒かかる `N`
の数」が増え、上記の実行時間はもっと小さくなるはずですが、まだそれを待っていられるほどの増加率では無いという話です。

プログラムを書く際、すべての箇所で時間計算量を厳密に意識すべきとまでは言いませんが、それでもクリティカルな箇所において高速化はできるべきです ([参考:
When to
optimize](https://en.wikipedia.org/wiki/Program_optimization#When_to_optimize))。もし高速化することでコードの可読性が落ちるのであれば、コメントやドキュメントの出番です。

なお、今考えてるのは時間計算量なのでメモリ量の増加は関係ありません。それは空間計算量やメモリの使い方の問題です。




部分的な回答：時間計算量を考えることは重要です。

[ムーアの法則](https://ja.wikipedia.org/wiki/%E3%83%A0%E3%83%BC%E3%82%A2%E3%81%AE%E6%B3%95%E5%89%87)を信じるのであればコンピューターの計算速度は指数的に増加していくわけですが、それでも多項式の次数レベルの時間計算量の差は大事です。現実的には目の前の問題をすぐ解いて欲しいわけで、コンピューターの計算速度が充分大きくなってくれるのを待つのでは現状まだ間に合いません。

特に問題となってくるのは、入力の数が多い場合です。手元の Python 環境(※)で試してみたところ、次の単純な O(N) のループでは、`N = 10
** 8` のとき実行におおよそ 1 秒かかりました。

[code]

    def repeat(n):
        for i in range(n):
            pass
    
[/code]

(※) 手元の環境：Core i7-8700, Python 3.7, Jupyter Notebook

このことから概算するに、同じ環境で同じ `N = 10 ** 8` を処理するとき、時間計算量によって次のように実行時間が変わってきます。

[code]

    O(N)   1 秒
    O(N²)  10⁸ 秒 ≒ 1000 日 ≒ 3 年
    O(N³)  10¹⁶ 秒 ≒ 3 億年
    
[/code]

数年待てば「実行に 1 秒かかる `N`
の数」が増え、上記の実行時間はもっと小さくなるはずですが、まだそれを待っていられるほどの増加率では無いという話です。

プログラムを書く際、すべての箇所で時間計算量を厳密に意識すべきとまでは言いませんが、それでもクリティカルな箇所において高速化はできるべきです ([参考:
When to
optimize](https://en.wikipedia.org/wiki/Program_optimization#When_to_optimize))。もし高速化することでコードの可読性が落ちるのであれば、コメントやドキュメントの出番です。

なお、今考えてるのは時間計算量なのでメモリ量の増加は関係ありません。それは空間計算量やメモリの使い方の問題です。

