为什么每个语句的以下代码都引用了大 O 常量(这里我使用 1 作为约定)?
我的意思是,如果数组大小变大,时间复杂度可能会变大,对吗?而且总数会越来越大,会不会影响复杂度?
伪代码:
def find_sum(given_array)
total = 0 # refers to O(1)
for each i in given array: #O(1)
total+=i #O(1)
return total #O(1)
TL;DR:因为 Big O 符号用于量化算法,考虑到它在输入增量时的行为方式。
我的意思是,如果数组大小变大,时间复杂度可能会变大,对吗?而且总数会越来越大,会不会影响复杂度?
您将算法所花费的时间误认为是时间复杂度。
让我们首先澄清Big O
当前上下文中什么是符号。从(来源)可以阅读:
Big O 表示法是一种数学表示法,它描述了当参数趋向于特定值或无穷大时函数的限制行为。(..)在计算机科学中,大 O 符号用于根据算法的运行时间或空间要求随着输入大小的增长而增长的情况进行分类。
非正式地,在计算机科学的时间复杂度和空间复杂度理论中,人们可以将Big O
符号视为算法的分类,分别具有关于时间和空间的某种最坏情况。例如O(n)
:
如果算法的时间/空间复杂度为 O(n),则称该算法采用线性时间/空间或 O(n) 时间/空间。非正式地,这意味着运行时间/空间最多随输入(source)的大小线性增加。
所以对于这段代码:
def find_sum(given_array)
total = 0
for each i in given array:
total+=i
return total
复杂性是O(n)
因为随着输入的增加,复杂性线性增长而不是恒定的。更准确Θ(n)
。
IMO 找出复杂性不是很准确,例如:
def find_sum(given_array)
total = 0 # refers to O(1)
for each i in given array: #O(1)
total+=i #O(1)
return total #O(1)
由于Big O
符号表示一组具有一定渐近上限的函数;正如人们可以从源代码中读取的那样:
Big O 表示法根据函数的增长率来表征函数:具有相同增长率的不同函数可以使用相同的
O
表示法来表示。
更准确的是:
def find_sum(given_array)
total = 0 # takes c1 time
for each i in given array:
total+=i # takes c2 time
return total # takes c3 time
所以时间复杂度为c1 + n * c2 + c3
,可以简化为 n。由于这个函数的下界和上界是相同的,我们可以使用Θ(n)
代替O(n)
。
本文收集自互联网,转载请注明来源。
如有侵权,请联系 [email protected] 删除。
我来说两句