大O表示法(Big0)

首先了解两个概念

时间复杂度：估算程序执行的次数

空间复杂度：估算程序所占用的存储空间

8 = 2^3 = log2(8) 用logn表示

16 = 2^4 = log2(16) 用logn表示

统一表示为log2(n) 用大O表示O(logn)

1+2*log2(n)+log2(n) (1+3n) = 1+3log2(n)+2 nlog2(n)=O(logn+nlogn)

=O(nlogn)

注意：大O表示法紧紧是一种粗略的分析模型，是一种估算，能帮助我们短时间内了解一个算法的执行效率

时间复杂度：大O表示渐进的时间复杂度

数据规模较小时对比

数据规模比较大时对比

X 数据规模

Y 执行的时间复杂度

https://leetcode.com

https://leetcode-cn.com

大O 就是 时间复杂度。

时间复杂度是大概的描述一个算法的用时（实际上从侧面的表达了他的效率）

你可以 把它 看成函数 y = f(x)一样。

O(n)中的n 代表 规模大小，这也表明了，时间复杂度 跟 规模的关系。

最好时间复杂度，通常指在最好情形下，这个算法用时。反之，最坏情况下的就是最坏时间复杂度。

通常 冒泡算法 的最坏时间复杂度就是O(2^n)，最坏情形是原序列 跟 排序后的序列完全相反。

it is O(n).

楼下的heptnaol回答是正确的，

为什么是大O,首先弄清楚大O是什么，有两种意思，一种是时间复杂度，一种是空间复杂度，

这里的大O就是 时间复杂度是O(n)，空间复杂度是O(1).

怎么看呢？

看这段代码片段

for(int i=0i<sizei++){

    if(arr[i] ==x){

        return i

    }

}

return -1

这段代码是什么意思，就是遍历数组，直到数组中的某个元素的值等于x的时候，则返回，

因为那个值出现在数组的位置是不确定的，可能是0，也可能是1，2，3，4.....n，所以就是O(n)，这个是时间复杂度，空间复杂度呢，就是看有没有动态分配内存，比如我新建了一个数组，将这个数据copy到另一个数组，再进行遍历，但是这并没有出现，所以就是O(1)，1代表的就是常量不会改变。

---