計算資源
在计算复杂性理论中,计算资源是一些计算模型在解决计算问题时使用的资源。
最简单的计算资源是计算时间,即解决一个问题所需的步骤数,以及内存空间,即解决问题时需要的存储量,但也有许多更复杂的资源被定义。 [需要引用]
一个计算问题一般[引用]是以其对任何有效输入的行动来定义的。问题的例子可能是 "给定一个整数n,确定n是否是素数",或者 "给定两个数字x和y,计算积x*y"。随着输入越来越大,解决一个问题所需的计算资源也会增加。因此,解决一个问题所需的资源是用渐进分析法来描述的,即把资源确定为输入的长度或大小的函数。资源的使用经常使用大O符号进行部分量化。
计算资源是有用的,因为我们可以研究哪些问题可以在每一种计算资源的一定量中计算出来。通过这种方式,我们可以确定解决问题的算法是否是最优的,我们可以对算法的效率做出说明。所有能用一定量的某种计算资源解决的计算问题的集合是一个复杂性类,而不同复杂性类之间的关系是复杂性理论中最重要的课题之一。
描述普遍可得的计算设备
"计算资源 "一词通常被用来描述可访问的计算设备和软件。参见公用计算。
计算能力的形式化量化
在正式量化计算能力方面已经有了一些努力。有界图灵机已经被用来为特定的计算建模,使用状态转换的数量和字母大小来量化解决一个特定问题所需的计算努力。[1][2]
參考資料编辑
- ^ Gregory J., Chaitin. On the Length of Programs for Computing Finite Binary Sequences (PDF). Journal of the ACM (JACM). 1966, 13 (4): 547–569 [2007-09-25]. doi:10.1145/321356.321363. (原始内容 (PDF)存档于2007-02-05).
- ^ Sow, Daby; Eleftheriadis, Alexandros. Representing Information with Computational Resource Bounds (PDF). Signals, Systems & Computers. Conference Record of the Thirty-Second Asilomar. Volume 1: 452–456. 1998 [2007-09-25]. ISBN 0780351487. 10.1109/ACSSC.1998.750904. (原始内容存档 (PDF)于2017-09-21).
🔥 Top keywords: Baike: 首页Special:搜索毛泽东家族榮耀之繼承者天之驕女鐵拳英雄九龍城寨之圍城黃循財背着善宰跑篠崎泫妮妃雅新生 (网络剧)劉偉健斯洛伐克习近平劉俊謙 (香港)李显龙歌手2024佛誕淚之女王2024年泰國羽球公開賽新加坡總理邊佑錫新加坡Energy (組合)庆余年九龍寨城六四事件家族榮耀金智媛彌助菲律宾胖猫跳江事件劉寶傑DAY6林峯張文傑李光耀神耆小子張鳳妮黃世聰Seventeen (組合)维基百科願榮光歸香港中華民國鬼滅之刃 柱訓練篇2024年英雄联盟季中邀请赛中华人民共和国TripleS金秀賢 (男演員)罗伯特·菲佐井柏然2024年世界女排联赛黃偉哲怪獸8號佘詩曼Foodpanda金惠奫新加坡总统香緹·摩爾于北辰 (1968年)王嘉爾笑看風雲排球少年!!角色列表林飛帆郭葦昀馴鹿寶貝翁靜晶猩球崛起:王國誕生ILLIT尼古拉·約基奇春色寄情人周殷廷鬼滅之刃排球少年!!吳釗燮逆天奇案2不夠善良的我們BABYMONSTER李正皓尚达曼BOYNEXTDOOR胡子彤IVE (組合)陳靜 (香港)香港吴作栋黃道十二宮凡希亚·奥伊亚胡宇威長洲太平清醮張員瑛搜查班長1958伍允龍习明泽黄岩岛賴清德偶然遇見的你虽然不是英雄