【算法与数据结构】前言
算法与数据结构是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_0>0 ∃c1,c2,n0>0 使得 ∀ 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_0>0 ∃c,n0>0 使得 ∀ 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_0>0 ∃c,n0>0 使得 ∀ 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(n+1)}2
2n(n+1)，可以将这种情况下的时间复杂度表达为
n
(
n
+
1
)
2
=
Θ
(
n
2
)
\frac{n(n+1)}2=\Theta(n^2)
2n(n+1)=Θ(n2)。
同理，我们可以在分析各种情况的基础下计算出三种时间复杂度，一般取平均时间复杂度和最坏时间复杂度来比较算法的速度。
空间复杂度
空间复杂度是描述算法消耗空间的语言。
空间复杂度直接定义对变量的数量计算即可。
空间复杂度非常简单，就不多说了。
N e x t : Next: Next: