算法的时间复杂性与问题的什么因素相关?

发布网友 发布时间：2022-04-19 21:25

我来回答

共5个回答

懂视网 时间：2022-04-20 01:46

算法的时间复杂度与问题的规模有关。在计算机科学中，算法的时间复杂度是一个函数，它定性描述该算法的运行时间。这是一个代表算法输入值的字符串的长度的函数。

　　

　　时间复杂度常用大O符号表述，不包括这个函数的低阶项和首项系数。使用这种方式时，时间复杂度可被称为是渐近的，亦即考察输入值大小趋近无穷时的情况。

　　

　　为了计算时间复杂度，通常会估计算法的操作单元数量，每个单元运行的时间都是相同的。因此，总运行时间和算法的操作单元数量最多相差一个常量系数。相同大小的不同输入值仍可能造成算法的运行时间不同，因此我们通常使用算法的最坏情况复杂度，记为 T（n），定义为任何大小的输入n所需的最大运行时间。另一种较少使用的方法是平均情况复杂度，通常有特别指定才会使用。时间复杂度可以用函数 T（n） 的自然特性加以分类。

热心网友 时间：2022-04-19 22:54

算法的时间复杂度和问题有关系但不能说是什么相关，因为一个问题很有可能有许许多多类算法，但是它们的时间复杂度不同，如大家最熟悉的排序问题我知道的就有10种左右算法，它们复杂度显然是不一样的。
这是一个概念问题，算法和问题是相联系的但是不是一一对应的。问题是存在的，算法是设计的，算法的时间复杂度除了和问题本身有关外还和设计者的水平，计算机类型等其它因素有关系。
你的问题是说一个问题的最好的算法的时间复杂度和问题的哪些因素相关么？
如果是这样我到是认为，一个问题的最优的算法的时间复杂度是这个问题本质的属性。这是我自己的理解，我认为理论上解决每个问题都会存在某个时间复杂度的下限，这个下限和这个问题的分类有关。如P类，NP类，NPC类等等 。
另外再比如说排序问题，我们可以用信息论简单地证明基于比较的排序算法理论时间复杂度下限为O(nlogn)，还可以证明NPC类问题可以被归约为一个相同的问题，而这个问题的时间复杂度下限是未知的（这还是疑难问题）。

热心网友 时间：2022-04-20 00:12

①问题的输入规模n
②数据的初始状态Xi
③算法策略（步骤之间的依赖关系、分成子问题，前后问题动态规划，问题解决的方式：迭代和递归等）

热心网友 时间：2022-04-20 01:47

问题的规模（n），算法的输（I），入算法本身（a）

热心网友 时间：2022-04-20 03:38

问题的规模