今天 Hackerrank 的主題是探討時間複雜度，透過的題目是給定一個整數，看看這個整數是不是質數。假設這個質數是 n 的話，希望解法的時間複雜度是 O(根號n)。然後我們也會來看看這四個語言要怎麼樣來計算程式運行時間囉！

Python 3

from math import sqrt

def isPrime(n):
    for i in range(2, int(sqrt(n))):
        if n % i is 0:
            return False
    return True

n = int(input())
if n >= 2 and isPrime(n):
    print("Prime")
else:
    print("Not prime")

• 這裡做的事情滿簡單的，可以看到最主要的是 isPrime 這個 Function 就是在計算 input n 是否是個質數。概念上是先取其根號，並且看 n 能不能被 2 到 根號n 之間的數字給整除，都不行就是質數，反之則不是囉！
• 這裡來介紹一下用來計算時間複雜度的 Library timeit，功用是讓我們量測一小段程式碼的時間。以下面的程式碼為例，我們這裡是把要測試的程式碼放在 code_to_test 這個字串裡面，測試把 100000 個數字加到 List 的時間。再來我們把這段程式碼作為 timeit 這個 Function 的第一個參數，而 number=100 代表我希望跑 100 次，而結果自然也要除以 100，最後得到平均的 elapsed_time 囉！更多關於 timeit 可以參考這裡。至於為什麼不直接取系統時間相減呢？因為 timeit 取時間的時候會自動判斷 OS 來使用相對應用來存取系統時間 Function，timeit 此時也能夠暫時 Disable GC 來避免干擾實驗，最後就是 timeit 提供很多參數，像是 number 來更方便使用囉！

import timeit
code_to_test = """
a = range(100000)
b = []
for i in a:
    b.append(i)
"""
elapsed_time = timeit.timeit(code_to_test, number=100)/100
print(elapsed_time)