什麼意思是'輸入中位數的多項式'？

因此，我有一門課程，其中有一些關於複雜性理論的問題，我有一些問題，PRIMES，它在NPTime複雜性類中。什麼意思是'輸入中位數的多項式'？

這一切都很好。

拋出我的東西是一個問題，想出一個計算（a^p）mod（b）的多項式時間算法。它必須是輸入大小的多項式（不是位）。

這是後面的句子，讓我困惑。

這是它失去我的地方！當然，假設一個蠻力嘗試（所有值介於2和sqrt（n）之間），會給出2^NoBits這是指數？！

現在我不想要答案！這是我的課程，所以我不能要求這個。我只想清楚「輸入比特數中的多項式」是什麼意思。向你的孩子解釋它;）

2015-12-01 David S

通常在處理算法和算法運行時間/複雜度時，你在輸入的大小上談論它。如果你有n個數字要排序，你可以用O（n^2）或O（n * log（n））等方式來衡量排序算法的時間複雜度。在這裏，他們所說的是他的大小輸入是輸入數字中的位數。 – Gopala

它說的基本上是蠻力嘗試不夠好。您只需要一個只能大致嘗試'（logN）^ k'數字的算法，其中'k'是一個正整數常量。（而'logN'當然大致是'N'中的數字位數。） – biziclop

意思是，如果n是輸入大小，則在大O符號中，O（n），O（log n），O（n^2），..從來沒有O（2^n）。 –

你有3個號碼，a,p和b。每個人可以是任何大小。 1. 10. 123_456_789。無限。

當我們將它們寫入基2中時，每個都是一些位數，然後是該位串。所以1，110，111010110111100110100010101.每一個都是一些比特數。 1,2,27。位數的總和就是你輸入的總大小。 30.

您的算法應該足夠高效，以至於存在一些多項式p(x)其中x是輸入中位數的總和，這是您的計算需要多長時間的上限。

尤其要注意的是，您不希望乘以a本身p次！

2015-12-01 18:55:24 btilly

回答