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

Question

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

Answer 1

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