iT邦幫忙

第 11 屆 iT 邦幫忙鐵人賽

DAY 25
0
自我挑戰組

資訊工程大補帖系列 第 25

資工補帖-Day 25-計算機演算法

演算法

一種愛恨交織的課程

解題目

  • 使用 Big O 、 Ω 以及 Θ 的定義,證明 8n^2+12? ∈ ?(?^2)

Let c = 10,
當 n>6, 8n^2+12?<10?^2 恆成立
8n^2+12? ∈ ?(?^2)

Let c = 1,
當 n>0 , 8n^2+12? > ?^2 恆成立
8n^2+12? ∈ Ω(?^2)
因為
8n^2+12? ∈ ?(?^2) ∩ Ω(?^2)
所以
8n^2+12? ∈ ?(?^2)

  • 試說明何為 P、何為 NP、何為 NP-complete

P 是所有可以被多項式時間必然式演算法(Polynomial-time deterministic algorithm) 解決之決策問題的集合。
NP 是所有可以被多項式時間非必然式演算法(Polynomial-time deterministic algorithm) 解決之決策問題的集合,即可以由一個多項式時間必然式演算法檢核任意對於該問題解答之猜測是否為正確解。
NP-complete,一個決策問題的集合,且任意屬於該集合之決策問題皆符合下列兩個條件:
(1) 其為 NP
(2) 任意 NP 問題都可以於多項式時間內化約成該集合中的任一問題


上一篇
資工補帖-Day 24-線性代數關鍵字
下一篇
資工補帖-Day 26-自己在大學開了一堂通識(1)
系列文
資訊工程大補帖30

尚未有邦友留言

立即登入留言