What is the Complexity of Find() Function
This question already has an answer here:
To begin with, the first version does in the worst case n iterations, and, in each iteration, does a constant number of operations. The second version does in the worst case n / 2 iterations, and, in each iteration, also does a constant number of operations, but a larger constant. Thus, there is no reason to think that the first is O(n) and the second is O(n / 2).
In any case, O(n) = O(n / 2). By the definition of O, O(n) means that there is a constant c1 such that for every n > n1,
f(n) < c1 n.
Similarly, O(n / 2) means that there is a constant c2 such that for every n > n2,
f(n) < c2 n / 2 = (c2 / 2) n.
Since for any n > max(n1, n2) the inequality holds for c1 = c2 / 2, each of these two implies the other one.
链接地址: http://www.djcxy.com/p/39360.html上一篇: 以下程序的时间复杂度是多少？
下一篇: Find（）函数的复杂性是什么？