次数O(log2)中的O什么意思

次数O(log2)中的O什么意思
次数O(log2)中的O什么意思

次数O(log2)中的O什么意思
算法时间复杂性分析是以原操作执行频度f（n）的阶（order）来表示时间复杂性的,其中n是问题的规模大小或者理解为算法所处理的数据总量.这是一种渐近（asymptotic）表示,数学上用O（f（n））来表示.O读做“大欧”（BigO）.
O（f（n））是上界概念的一种推广,表示存在一个正的常数M使得由O（f（n））表示的数xn,对于所有的n≥n0都满足xn≤Mf（n）.对O（f（n））的精确描述是,O（f（n））是一类函数g的集合,该类函数满足存在一个正常数M,使得对于所有大于n的数,满足g（n）≤Mf（n）.
在含有O的等式中,采用单向相等的约定,即一个等式的右边不能给出比左边更多的信息,右边乃是左边的“粗略化”