为什么我们要测量时间复杂度而不是步骤复杂度？

Question

当我第一次上算法课的时候，我搞不懂在谈论渐近时间复杂性时实际测量的是什么，因为它肯定不是计算机运行程序所需的时间。相反，我的心智模型是，我们测量的是渐近步长复杂性，也就是CPU运行算法所需步骤的渐近数。

我们为什么考虑时间复杂度而不是步骤复杂度，并讨论一个算法花费多少时间，而不是一个CPU执行该算法所需的步骤(渐近)？

Answer 1

实际上，步骤的数量是决定因素，条件是步骤的持续时间不依赖于输入--它不应该比某些选定的恒定时间花费更多的时间。

这个恒定的时间到底是什么，将取决于你运行它的系统。有些CPU比其他CPU更快，有些CPU更擅长于一种操作，而在另一种操作中则更少。因此，两个不同的步骤可以表示不同的时间:在一个CPU上，步骤A可以以比步骤B更短的延迟执行，而在另一个CPU上，则可能是相反的。甚至可能是，在同一CPU上，步骤A有时比其他时间执行得更快(例如，由于CPU管道中的一些有利条件)。

所有这一切都不可能说一些有用的东西，只要衡量时间运行一步。相反，我们认为算法中所识别的所有不同类型的“步骤”都有一个最大时间(对于给定的CPU)，因此单个步骤的执行永远不会超过该最大时间。

因此，当我们谈到时间复杂性时，我们确实谈到了算法所需的时间。如果算法具有O(N 2)的时间复杂度，就意味着我们可以找到一个值minN和一个常数时间C(我们可以自由地选择它们)，这样，对于n个>= minN，运行该算法所需的总时间T是以T

简而言之，我们在步骤和时间单位之间建立了一个等价关系，从而保证一个步骤的执行受到该时间单位的限制。

Answer 2

你说得对，我们测量算法在图灵机上运行的计算步骤。然而，我们并不是每一步都算在内。相反，我们通常对算法的运行时差异感兴趣，而忽略常量因素，就像使用O-表示法时一样。

此外，我相信这个词是相当直观的把握。当你谈论一个算法需要多长时间时，每个人都对你的意思有了基本的理解(我甚至可以向我母亲解释)。但是，如果您讨论一个算法需要多少个步骤，您可能会发现自己正在讨论计算模型(什么样的CPU)。

时间复杂性这一术语并没有错(事实上，我相信这正是我们所要寻找的)。步骤复杂性一词将具有误导性。