时间复杂度—常数和线性复杂度(1)
大O符号是由德国数论学家保罗·巴赫曼（Paul Bachmann）在其1892年的著作《解析数论》（Analytische Zahlentheorie）首先引入的。 我们常用大O表示法表示时间复杂度，注意它是某一个算法的时间复杂度。 大O表示只是说有上界，由定义如果f(n)=O. (n)，那显然成立f(n)=O
为什么 big O 符号是有用的？那么什么是大 O 符号？ 大 O 符号是用来分析一个算法的效率，表示随着输入接近无穷大，这意算法的输入大小的增长速度。
例如，假设我们有一个理发师，他平均需要 30 分钟为一个顾客提供理发服务。随着他的顾客的队伍的增加，他工作时间所需的时间将与排队等候的顾客数量成线性比例。
这是因为他通常为每个顾客理发所需的时间始终是固定的，也就是大约 30 分钟。这让我们大致了解了为 10 个、20 个顾客甚至100,000 个顾客需要多长时间。
因为理发时间是固定的，所以总是可以通过将顾客的数量乘以 30分 钟来计算出他服务任何数量的顾客所需的时间。考虑到这一点，我们可以把他的效率归为线性。
如果用大O术语来说就是 O(n)O(n)O(n)，其中 n 等于顾客的数量 ，理发师完成工作所需的时间与顾客的数量呈线性或比例关系，我们用同样的技术来确定算法的效率，可以通过对一个给定的函数进行分类来了解其时间效率的变化情况。
function linearFunc(arr){ for (let i = 0; i < arr.length; i++) { console.log(1000 * 10000); } } const arr = [1,2,3,4,5,6,7]; linearFunc(arr); 复制代码让我们创建一个容易理解的函数，函数效率和理发师类似。 因此，这个函数与我们的理发师属于同一线性。函数的输入是一个数组，每一个迭代循环体中计算 1000*100,000 耗时是固定的，这个事件根循环次数无关，表达式用时间与理发时间是固定的。
对于上面函数，如果将数组的长度增加到 1000,000 然后将 console.log(1+1) 其实这个函数效率还是不变的，因为也就是和输入的一个线性关系。忽略所有这些常数，并说这个函数是线性扩展的，或者说是n的大O。
function linearFunc(arr){ for (let i = 0; i < arr.length; i++) { console.log(1000 * 10000); let something = 1000 * 1000 console.log(something) } } const arr = [1,2,3,4,5,6,7]; linearFunc(arr); 复制代码常量
常数是指任何不随函数的输入而变化的操作。下面函数中函数计算时间和返回值都是固定，不会随着输入而变换，这就是常数，对于常数复杂度是 O(1)O(1)O(1)
function constants(arr){ let result = 100*1000; return result } 复制代码function linearFunc(arr){ for (let i = 0; i < arr.length; i++) { console.log(1000 * 10000); let something = 1000 * 1000 console.log(something) } } 复制代码在这个函数里 for 是 O(n)O(n)O(n)，而其内部语句的时间复杂度都是 O(1)O(1)O(1)。
O(n)+O(1)+O(1)+O(1)O(n) + O(1)+ O(1)+ O(1)O(n)+O(1)+O(1)+O(1) 在这里我们只在乎时间复杂度较高的而会忽略时间复杂度较低级，这里O(1)O(1)O(1),所以上面函数是O(n)O(n)O(n)
作者：ti138729
链接：https://juejin.cn/post/7022227393549090847