iT邦幫忙

第 11 屆 iT 邦幫忙鐵人賽

DAY 26
1
Software Development

30 天把自己榨好榨滿的四週四語言大挑戰!系列 第 26

[Day 25] 與時間複雜度的競賽

今天 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)

上一篇
[Day 24] 一條獨一無二的鏈
下一篇
[Day 26] 以組合代替繼承?
系列文
30 天把自己榨好榨滿的四週四語言大挑戰!30

尚未有邦友留言

立即登入留言