算法中的运算计数方法
有多种方法可以估算某种算法的成本。通过使用操作计数之一。我们可以通过选择不同的运算之一来估计算法的时间复杂度。这些就像加,减等。我们必须检查完成了多少这些操作。这种方法的成功取决于我们识别出造成大部分时间复杂性的操作的能力。
假设我们有一个大小为n[0到n-1]的数组。我们的算法将找到最大元素的索引。我们可以通过计算在数组的每对元素之间执行比较操作的次数来估算成本。我们必须记住,我们只会选择一种操作。在该算法中,几乎没有其他操作,例如迭代变量i的递增或为索引分配值等。但是在这种情况下不考虑它们。
算法
getMax(arr, n): index := 0 max := arr[0] for i in range 1 to n - 1, do if arr[i] > max, then max := arr[i] index := i end if done return index
我们必须选择执行时间最多的那些操作才能估算成本。假设我们有一个气泡排序算法,并且计算交换操作。然后,我们必须记住,何时最大。这将在分析过程中为我们提供最大的结果。