深圳商城手机网站建设,中国站长之家网站,steam交易链接在哪里看,网页设计页面算法与数据结构是OI中不可或缺的一部分。
今天#xff0c;让我们走进算法与数据结构独特世界。 性能
算法与数据结构都是完成任务的方法。 方法就要有性能。 有效率就有描述性能的语言。 这就是复杂度。
复杂度的描述
由于复杂度描述的是大致性能#xff0c;所以采用的是…算法与数据结构是OI中不可或缺的一部分。
今天让我们走进算法与数据结构独特世界。 性能
算法与数据结构都是完成任务的方法。 方法就要有性能。 有效率就有描述性能的语言。 这就是复杂度。
复杂度的描述
由于复杂度描述的是大致性能所以采用的是近似的方法将复杂度用一个函数和一个记号表示记号称为渐进记号。 渐进记号有三种实际上有六种在这里看但一般只用这三种 f ( n ) Θ ( g ( n ) ) f(n)\Theta(g(n)) f(n)Θ(g(n))其中 f ( n ) , g ( n ) f(n),g(n) f(n),g(n) 为函数下同 它表示 f ( n ) f(n) f(n) 在 g ( n ) g(n) g(n) 的两个常数倍之间。 形式化的 ∃ c 1 , c 2 , n 0 0 \exist c_1,c_2,n_00 ∃c1,c2,n00 使得 ∀ n ≥ n 0 \forall n\ge n_0 ∀n≥n0 0 ≤ c 1 ⋅ g ( n ) ≤ f ( n ) ≤ c 2 ⋅ g ( n ) 0\le c_1\cdot g(n)\le f(n)\le c_2\cdot g(n) 0≤c1⋅g(n)≤f(n)≤c2⋅g(n) f ( n ) O ( g ( n ) ) f(n)O(g(n)) f(n)O(g(n)) 它表示 f ( n ) f(n) f(n) 在 g ( n ) g(n) g(n) 的某个常数倍以下。 形式化的 ∃ c , n 0 0 \exist c,n_00 ∃c,n00 使得 ∀ n ≥ n 0 \forall n\ge n_0 ∀n≥n0 0 ≤ f ( n ) ≤ c ⋅ g ( n ) 0\le f(n)\le c\cdot g(n) 0≤f(n)≤c⋅g(n) f ( n ) Ω ( g ( n ) ) f(n)\Omega(g(n)) f(n)Ω(g(n)) 它表示 f ( n ) f(n) f(n) 在 g ( n ) g(n) g(n) 的某个常数倍以上。 形式化的 ∃ c , n 0 0 \exist c,n_00 ∃c,n00 使得 ∀ n ≥ n 0 \forall n\ge n_0 ∀n≥n0 0 ≤ c ⋅ g ( n ) ≤ f ( n ) 0\le c\cdot g(n)\le f(n) 0≤c⋅g(n)≤f(n)
复杂度的计算简单来说如下
舍去各项常数舍去除最高次项外的其它项若数据范围特殊可保留一定项余下的即为所求
对于OI来说算法与数据结构需要达到一定的时间和空间性能对应的产生了时间复杂度和空间复杂度
时间复杂度
时间复杂度是描述算法消耗时间的语言。 时间复杂度分为三种最好时间复杂度最坏时间复杂度平均时间复杂度顾名思义。 OI赛制下一般不考虑最好时间复杂度。
时间复杂度的计算
取某种情况例如输入序列 a a a 按升序排序 ∀ n ≥ n 0 \forall n\ge n_0 ∀n≥n0在该条件下有执行次数始终为 n ( n 1 ) 2 \frac{n(n1)}2 2n(n1)可以将这种情况下的时间复杂度表达为 n ( n 1 ) 2 Θ ( n 2 ) \frac{n(n1)}2\Theta(n^2) 2n(n1)Θ(n2)。 同理我们可以在分析各种情况的基础下计算出三种时间复杂度一般取平均时间复杂度和最坏时间复杂度来比较算法的速度。
空间复杂度
空间复杂度是描述算法消耗空间的语言。 空间复杂度直接定义对变量的数量计算即可。 空间复杂度非常简单就不多说了。 N e x t : Next: Next:
算法前言
数据结构前言
