指數時間

The name of the pictureThe name of the pictureThe name of the pictureClash Royale CLAN TAG#URR8PPP





在計算複雜度理論中，指數時間指的是一個問題求解所需要的計算時間m(n)，依輸入数据的大小ndisplaystyle nn而呈指數成長（即輸入数据的數量依線性成長，所花的時間將會以指數成長）。


以數學術語來說，便是若存在 k > 1，則此m（n） = Θ(kn)且存在c使得m（n） = Ο（cn）


计算机科学家認為多項式時間是快的，而其他類型的計算時間是慢的。指數時間因此被認為是慢的類型。有很多演算法計算時間慢過多項式時間，因此被稱為超多項式時間，但又快過指數時間，也因此又被稱為次指數時間，它們也被認為是慢的演算法。此類問題中最著名的便是整數分解。



參閱


  • 計算複雜度理論

  • 多項式時間

  • 常數時間

  • 線性時間

  • 演算法

  • 大O符號

-

Popular posts from this blog

用户:Ww71338ww/绘画

Image
Clash Royale CLAN TAG #URR8PPP 你好～！欢迎来到萌娘百科！ 如果您是第一次来到这里，点这里加入萌娘百科! 欢迎具有翻译能力的同学～有意者请点→Category:需要翻译的条目← 如果您在萌娘百科上发现某些内容 错误/空缺 ，请 勇于 修正/添加！ 编辑萌娘百科其实很容易！ 觉得萌娘百科有趣的话，请推荐给朋友哦...
Read more

自由群

Image
Clash Royale CLAN TAG #URR8PPP 由兩個元素a, b 生成的自由群的凱萊圖 在數學中，一個群 Gdisplaystyle G 被稱作 自由群 ，如果存在 Gdisplaystyle G 的子集 Sdisplaystyle S 使得 Gdisplaystyle G 的任何元素都能唯一地表成由 Sdisplaystyle S 中元素及其逆元組成之乘積（在此不論平庸的表法，例如 st−1=su−1ut−1displaystyle st^-1=su^-1ut^-1 之類）；此時也稱 Gdisplaystyle G 為集合 Sdisplaystyle S 上的 自由群 ，其群...
Read more

卑爾根

Image
Clash Royale CLAN TAG #URR8PPP 卑尔根 Bergen 城市 Kommune av Bergen 旗幟 徽章 卑爾根在霍达兰郡的位置 卑尔根 卑爾根在挪威的位置 坐标： 60°22′N 05°24′E  /  60.367°N 5.400°E  / 60.367; 5.400 坐标： 60°22′N 05°24′E  /  60.367°N 5.400°E  / 60.367; 5.400 國家   挪威 郡 霍达兰郡 建立 1070年之前 政府  • 市長 Marita Moltu （KrF） 面积  • 城市 464.71 平方公里（179.43 平方英里）  • 陸地...
Read more