[算法]计算算法的复杂性 - 算法的复杂性

[算法]计算算法的复杂性 – 算法的复杂性

七月 23, 2014 nguyenvanquan7826 算法 10 回复

内容
分析算法的需要
 程序的执行时间
 加息和算法的复杂性
 计算算法复杂度
 回归方程求解

更新日期 28/05/2014 – 在一个更容易看到拼写和演示文稿编辑公式.
周围有数码锁许多问题, 尤其是算法的复杂性. 本文将提出的问题, 介绍了相关的概念和如何整合算法的复杂性.
在课程的分析算法参考文章 - CTU

我. 必要性分析算法

虽然解决一个问题，我们可以有许多不同的算法, 问题是，以评估其选择一个好的算法，算法的需要 (最为). 通常情况下，我们将根据以下标准:
1. 算法的正确性.
2. 简单的算法.
3. 快速算法的实现.

要求 (1), 查询的算法，我们可以安装算法和对多个采样数据的执行，然后检索结果的正确性与已知的结果进行比较. 其实，不知道如何做到这一点，因为该算法能正确地与所有的数据，我们已经尽力了，但错了一定的数据集. 此外，这种方法只是发现算法错误的，但没有证明它正确. 需要用数学证明了算法的正确性. 当然，这不是那么简单的，我们也不会在这里提到.
当我们编写一个程序使用了几次，则Yü弥合ê (2) 是最重要的. 我们需要一个算法容易编写程序，快速得到结果, 该计划的实施时间不应该反正兑现，因为该程序只用于单独几次.
然而，当一个程序被多次使用，它要求程序的节省时间的实施特别是对于那些这样做的时候需要数据的程序非常重要，需要很大的进口 (3) 会慎重考虑. 我把它叫做算法的有效执行时间.

II. 时间程序

一种方法，以确定一次性执行算法的效果被编程它，并测量在计算机上活动的执行时间，以确定所述一组选择的输入的. 执行时间不仅取决于依赖于一组计算机的指标算法, 电脑的质量和程序员的技巧. 执行还可以进行调整，以使好的一套特定的数据来选择. 为了克服这个障碍, 计算机科学家都接受了访问时间复杂度算法执行的基本措施. 远期疗效将把这项措施，特别是对于时间复杂度在最坏的情况下.
程序执行时间.
时间做一个程序，它是输入大小的函数, 符号为T(ñ) 其中n是大小 (大小) 对数据的. 计划ñ金额做了一些时间T(ñ) = Cn，其中c为常数. 程序执行时间是一个功能不健全, 即Ť(ñ) ≥ 0 对所有的n≥ 0.
的措施执行时间单位.
单位T(ñ) 测量的不单位为正常时间小时, 瞬间… 在一个理想的计算机来执行，其通常是通过命令的数目来确定. 当我们说一个程序的执行时间为T(ñ) = CN，这意味着该方案应道道执法指令.
在最坏的情况下执行时间.
一般情况下，方案实施期间不仅取决于规模，还取决于数据的性质. 意味着在相同大小的数据，但该节目的持续时间可能会发生变化. 按照从小到这种方案的整数, 当我们进入的时候我们没有输入次序井然其他的排列顺序执行时间, 或者当我们输入的序列增加所花费的时间的顺序也是从我们进入了一个序列递减的顺序不同. 所以很多时候，我们见T(ñ) 该方案在对输入大小n最坏的情况下的持续时间, 即: 牛逼(ñ) 为实现对同一大小N的所有数据程序的最大时间.

III. 率的提高和算法复杂度

率提高
有人说，没有负面的函数T(ñ) 保证金增加 (增长率) ˚F(ñ) 如果 $\exists \ C, N_{0} \ | \ T(n) \leq Cf(n), \forall \ n \geq N_{0}.$
我们可以证明 对于非负函数T(ñ) 任何, 我总能找到生长速率f(ñ) 其.
假设 $T(0) = 1,\ T(1) = 4$ 和一般: $T(n) = (n+1)^{2}$ .
地方 $\ N_{0} = 1, \ C = 4$ 然后对所有的n≥1我们很容易证明:
$T(n) = (n+1)^{2} \leqslant 4n^{2}, \forall \ n \geq 1$ , 即，加息 $\ T(n) = n^{2}$ .
该函数的增长速度 $\ T(n) = 3n^3 + 2n^2 = n^3$ .
的确, 给 $\ N_{0} = 0, \ C = 5$ 这是很容易证明 $\forall n \geq 0 \Rightarrow 3n^3 + 2n^2 \leqslant 5n^{3}$
的算法复杂度的概念
假设我们各有两种算法P1和P2与执行时间:
$\begin{cases} T1(n) = 100n^2 & \text{ ty suat tang la } n^2 \\ T2(n) = 5n^3 & \text{ty suat tang la } n^3 \end{cases}$
该算法将执行得更快? 答案取决于数据的大小. ñ < 20 它会更快P1 P2 (T2<T1), 通过100n的较小5N ^ 3 ^ 2系数的系数 (5<100). 但是，当n > 20 上由较小100N ^ 2指数5N ^ 3的的指数另一方面 (2<3). 在这里，我们只应该感兴趣的情况下，n>20 因为当n<20 P1和P2的执行时间并不大和T1和T2之间的差可以忽略不计.
因此，逻辑上，我们考虑的增长速度是程序本身的实时审核的功能，而不是执行时间.
对于一个函数T(ñ), 牛逼(ñ) 所谓复杂˚F(ñ) 如果 $\exists \ C, N_{0} \ | \ T(n) \leq Cf(n), \forall \ n \geq N_{0}.$ (即Ť(ñ) 利润率增长为f(ñ)) 并用O(˚F(ñ)). (“细胞˚F(ñ)”)
$T(n)= (n+1)^2$ 余量增大为n ^ 2应 $T(n) = O(n^2)$
注意: 该(C.f(ñ))=的(˚F(ñ)) C是常数. 特别Ø(Ç) =的(1)

换句话说计算算法的复杂度是及时的功能块的功能. 因为在功能块C每个人的因素是没有意义的，所以我们不能忽视这样复杂的功能后常见的形式:
$logn, n, n^2, n^3, 2^n, n!m n^n$ .
最后三个功能被称为指数函数, 所谓多项式其他功能. 实时算法的复杂性是多项式函数，那么就是可以安装到执行上可接受的, 而该算法具有指数复杂，他们必须想方设法提高算法.
注意: 在LOGN我们不关心，因为它的基础 $log_{a}n = log_{a}b.log_{b}n = log_{b}n, b > 0$ (规则给系数后面会提到)
当涉及到的算法的复杂性，我们要谈谈计划的执行期的效果，所以我们可以看到该程序的门廊的实时确定确定的算法的复杂性.

IV. 计算算法复杂度

如何计算的算法的复杂性是一个问题，任何没有简单. 但是，我们可以遵循一些准则:
规则给定
如果P段程序执行时间T(ñ) =的(c1.f(ñ)) 以积极的常数C1
可考虑具有计算复杂的程序段是O(˚F(ñ)).
社区规则 – 取最大值
如果T1(ñ) 和T2(ñ) 两个程序P1和P2的执行期; 与T1(ñ)=的(˚F(ñ)), T2(ñ)=的(克(ñ)) 该周期的持续时间的两个连续的程序为T(ñ)=的(最大(˚F(ñ),克(ñ)))
首席执行官:
分配X:= 15消耗一定的时间或O-(1), 读取数据的命令readln(X) 消耗恒定时间或O-(1).
所以花费的时间都在连续的命令是O(最大(1,1))=的(1)
凸轮的
如果T1(ñ) 和T2(ñ) 两个程序P2和T1 P1va实施期(ñ) =的(˚F(ñ)), T2(ñ) =的(克(ñ)) 该程序段的持续时间两段嵌套Ť(ñ) =的(˚F(ñ).克(ñ))
分析程序的一般规则
– 每个分配的执行时间, 读, WRITELàÔ(1).
– 命令序列的执行时间是由社会规则确定. 所以这个时候是实施指挥，在指挥链最长的时间.
– 实施周期为周期结构最大的IF THEN要不然和时间后，再执行下面的命令来检查条件. 通常时间来检查的O条件(1).
– 循环的执行时间是总 (在所有迭代) 循环体的持续时间. 如果实时回路常数实施例中，循环的执行时间被集成实时迭代循环实施例.
首席执行官: 程序定时实施分类“泡沫”

procedure Bubble (var a: array[1..n] of integer);
var i,j,temp: integer;
begin
	for i:=1 to n-1 do					{1}
		for j:=n downto i+1 do				{2}
			if a[j-1]>a[j] then			{3}
			begin
				temp:=a[j-1];			{4}
				a[j-1]:=a[j];			{5}
				a[j]:=temp; 			{6}
			end;
end;

在冒泡排序算法, 我们将在第三章详细讨论 2. 这里, 我们只是感兴趣的算法的复杂性.
我们看到包括命令只重复整个程序 {1}, 为了笼 {1} 是有序 {2}, 为了笼 {2} 是有序 {3} 而为了笼子 {3} 是 3 连续订单 {4}, {5} 和 {6}. 我们将在复杂的顺序进行由内而外.
首先, 所有三个分配 {4}, {5} 和 {6} 在消费Ø(1) 时间, 一个比较[J-1] > 该[Ĵ] Ø很好地定位(1) 时间, 因此命令 {3} 消费Ø(1) 时间. 环 {2} 执行 (N-1) 时间, 每次时间为O(1) 所以循环 {2} 消费Ø((N-1).1) =的(N-1).环 {1} 与我运行重复 1 n-1个到循环的执行时间 {1} 并且也是该算法的复杂度:
$T(n) = \sum_{i=1}^{n-1}(n-i) = \frac{n.(n-1)}{2} = O(n^2)$
注意: 在循环不能确定迭代次数的情况下，我们必须在最坏的情况下迭代的次数.
顺序搜索. 搜索功能接收阵列正整数和整数x, 如果存在的元素的函数返回逻辑值TRUE[在] = X, 逆函数返回FALSE.
顺序搜索算法依次比较x与阵列A的元素, 启动[1], 如果存在[在] = X，然后停止并返回TRUE, 如果特征X的所有其它元件返回FALSE反之亦然.

FUNCTION Search(a:ARRAY[1..n] OF Integer;x:Integer):Boolean;
VAR i:Integer;
	Found:Boolean;
BEGIN
	i:=1; 											{1}
	Found:=FALSE; 									{2}
	WHILE(i<=n) AND (not Found) DO					{3}
		IF A[i]=X THEN Found:=TRUE ELSE i:=i+1; 	{4}
	Search:=Found; 									{5}
END;

我们看到命令 {1}, {2}, {3} 和 {5} 编织, 所以功能搜索的复杂性是最大的复杂 4 此命令. 不难看出，这三个订单 {1}, {2} 和 {5} 有复杂度为O(1) 所以功能搜索的复杂性是命令的复杂性 {3}. 为了笼 {3} 是有序 {4}. 命令 {4} 复杂度为O(1). 在最坏的情况下 (阵列的所有元素都具有一个不同的x) 循环 {3} 执行N次, 所以，我们个人有T(ñ) =的(ñ).
该方案的复杂性并没有调用的子程序递归
如果我们有一个程序与子程序不能递归, 计算程序的执行时间, 我们首先计算子程序的执行时间不调用子程序等. 然后我们计算子程序的执行时间只调用并计算出它们的执行期子程序. 我们将继续所有调用子程序的执行时间后评估每个子程序的执行时间的过程评价. 最后，我们计算时间主程序.
假设我们有一个称为继在一起图程序的系统:
dequy
程序的调用两个子程序是B和C, 节目B被称为2子程序B1和B2, 程序调用两个子程序B1是B11和B12.
为了计算A的执行时间, 它是根据以下步骤来计算:
1. 定时执行的C, B2, B11和B12. 因为这个子程序调用子程序的所有.
2. B1的计算执行时间. B1和B12 B11呼叫，因为B11和B12实施的那段时间已经在步骤计算 1.
3. B的计算的执行时间. 由于B称为B1和B2使B1的执行时间已在步骤中计算出 2 和B2的执行时间，在步骤计算 1.
4. A的计算执行时间. 由于A呼叫B和C B的执行时间已在步骤中计算出 3 和C的执行时间，在步骤计算 1.
我们可以按如下改写冒泡排序程序: 首先，我们写程序来实现完成交换两个元素彼此变化, 然后在程序泡泡, 在必要时，我们将调用这个过程交换.

procedure Swap (var x, y: integer);
var temp: integer;
begin
	temp := x;
	x := y;
	y := temp;
end;
procedure Bubble (var a: array[1..n] of integer);
var i,j :integer;
begin
	for i:=1 to n-1 do								{1}
		for j:=n downto i+1 do						{2}
			if a[j-1]>a[j] then
				Swap(a[j-1], a[j]);					{3}
end;

在写作上, 程序子程序调用泡泡交换, 由此计算出气泡的执行时间, 我们应该首先计算交换的执行时间. 掉期的持续时间显着为O(1) 因为它只盖 3 分配. 在泡泡, 命令 {3} 交换电话应该只花费Ø(1), 命令 {2} 执行N-1次, 每次耗时Ø(1) 应该花费Ø(N-1). 命令 {1} 执行N-1应:
$T(n) = \sum_{i=1}^{n-1}(n-i) = \frac{n.(n-1)}{2} = O(n^2)$
递归程序的分析
随着调用子程序递归程序, 一个人不能申请计算作为刚刚提出，因为递归程序将调用本身，如果方法则, 计算节目A的执行时间, 我们必须计算程序的执行时间，并不能结束的怪圈.
递归程序, 首先要建立回归方程, 那么回归方程, 递归方程将是节目的持续时间递归.
成立回归方程
递归方程是式表示T的关系(ñ) 和T(到), 其中T(ñ) 该节目的持续时间与输入大小为n, 牛逼(到) 与输入数据大小的程序的执行时间为k, ķ < ñ. 要建立方程递归, 它必须基于递归程序. 通常，一个递归程序来解决规模为n的问题, 必须有至少一个止挡用的情况下，特定n和递归调用来解决问题大小k (K0程序必须调用递归Giai_thua(N-1), 这个递归调用花费的T(N-1), 递归调用的结果后，, 方案必须乘以n个结果，并分配Giai_thua. 时间来执行乘法和分配恒定C2. 因此，我们有
$T(n) = \begin{cases} C1 & n=0 \\ F(T(n-1)) + C2 & n>0 \end{cases}$
这是一个递归公式来计算程序的执行时间递归Giai_thua.
我们认为该过程归并草图如下:

FUNCTION MergeSort (L:List; n:Integer):List;
VAR L1,L2:List;
BEGIN
	IF n=1 THEN RETURN(L)
	ELSE
	BEGIN
		Chia đôi L thành L1 và L2, với độ dài n/2;
		RETURN(Merge(MergeSort(L1,n/2),MergeSort(L2,n/2)));
	END;
END;

例如，排序列表L由 8 元素 7, 4, 8, 9, 3, 1, 6, 2 我们已经归并的模型说明如下:

归并函数有长度为n的列表，并返回一个排序列表. 过程合并接收的两个列表即将L1和L2长度为n / 2的每个列表它们混合在一起以获得n个元素无序列表. 合并算法的详细信息，我们将在后面讨论, 我们只注意到了一次合并长度为n / 2 O列表(ñ). 调用Ť(ñ) 在时间采取归并n个元素的列表，则T(N / 2) 在时间采取归并n / 2个元素的列表. 当L的长度 1 (N = 1) 该程序只能做一件事不仅是回报(L), 它的成本Ø(1) = C1时间. 在情况下，n > 1, 程序来执行递归调用MerSort两次L1和L2长度为n / 2因此时间调用两次这种递推为2T(N / 2). 还需要花费时间向列表分成两个相等L和混合两种结果列表 (合并). 它被确定为分割列表和合并的时间是O(ñ) = C2N. 因此，我们有如下回归方程:
$T(n) = \begin{cases} C1 & n=1 \\ 2T(\frac{n}{2}) + C2.n & n>1 \end{cases}$

该. 解决方案式监管

该方法检索:
使用递归来代替任意t(米) 以m<N于该PT的右侧，直到m = 1的.
首席执行官: 回归方程求解:
$T(n) = \begin{cases} C1 & n=1 \\ 2T(\frac{n}{2}) + C2.n & n>1 \end{cases}$

我有:
$T(n) = 2T(\frac{n}{2}) + C2.n$
$=2[2T(\frac{n}{2})+ C2.\frac{n}{2}] + C2.n = 4T(\frac{n}{4}) + 2.C2.n$
$=4[2T(\frac{n}{8})+ C2.\frac{n}{4}] + C2.n = 8T(\frac{n}{8}) + 3.C2.n$
= …
$=2^{i}.T(\frac{n}{2^{i}}) + i.C2.n$
联赛历史 $n=2^k$ 并在最后我们有我= j的.
$\Rightarrow T(n) = 2^{k}T(1) + kC2n$
那里:
$n=2^k \Rightarrow k = logn, T(1) = C1\\ \Rightarrow T(n) = 2^{k}T(1) + kC2n\\ \Rightarrow T(n) = n.C1 + C2.n.logn\\ \Rightarrow T(n) = O(n.logn)$

一般方法
划分问题转化为问题儿童和尺寸N / B的每一个问题. 和每一个这样的份额，直到问题小到足以解决 (递归). 而使用这种方法后，它已经表明，对回归方程:
$T(n) = \begin{cases} C1 & n=1 \\ aT(\frac{n}{b}) + C2.n & n>1 \end{cases}$
我有:
牛逼(ñ) = C1如果n = 1
ñ>1 我们有:
$乳胶Ť(ñ) = 开始{案件} 该(ñ) & \文本{ 如果 } 该 < b \\ O(n.log(n)) & \text{ if } a=b \\ O(n^{loga}) & \text{ if } a > b 端{案件}$

在课程的分析算法参考文章 – CTU

你可能会喜欢:

10 在回应 [算法]计算算法的复杂性 – 算法的复杂性

范文逸 说:

三月 13, 2016 在 4:16 下午

文章的最后一段乳胶对不起啦一?

回复
1. 恩·武 说:
  
  十一月 7, 2017 在 1:51 下午
  
  显然la` v EM
  
  回复
奎武说:

三月 11, 2018 在 12:24 是

如果你不喜欢这种算法是多先生 ?
为(长长I = 0;在>桩[在];
为(长长J = 0;Ĵ<=我;J )
{
如果(桩[在]<雪[Ĵ])
{
雪[Ĵ] -=桩[在];
总和+ =桩[在];
}
其他
{
总和+ =雪[Ĵ];
雪[Ĵ] = 0;
}
}
COUT<<总和<<" ";
}

回复
1. nguyenvanquan7826 说:
  
  三月 15, 2018 在 10:23 是
  
  该(N ^ 2) NHE.
  
  回复
ngocthach 说:

五月 15, 2018 在 2:40 下午

CT上的这是什么珍贵的申请a..Help我的复杂性
诠释Tohop(INTñ, 时int k){
如果(满足K == 0||满足K ==Ñ)
返回 1;
返回( Tohop(N-1，K-1)+Tohop(n-1个中，k)

回复
肯特说:

五月 29, 2018 在 11:07 是

让我问的这个程序段的复杂度是多少，先生:
为 (I = 0; 在<ñ; 我 )
ķ++;
为 (I = 0; 在<ñ; 我 )
为 (J = 0; Ĵ<ñ; J )
ķ++;

回复
芽说:

五月 3, 2019 在 8:23 下午

请问这对所有患者爵士范围C1杂志
包doannhom;

进口java.util.Arrays中;

公共类ConvertBTtoBST {
公共静态类节点{
int数据;
左节点;
节点权;

公共节点(int数据){
this.data =数据;
this.left = NULL;
this.right = NULL;
}
}
公共节点根;

INT[] treeArray;
INT指数= 0;

公共ConvertBTtoBST(){
根=空;
}
公共节点insertLevelOrder(INT[] ARR, 节点根, INT I){
如果 (我结束) {
返回NULL;
}
INT中旬= (开始 + 比) / 2;
节点node =新节点(treeArray[中]);
node.left = createBST(开始, 中 – 1);
node.right = createBST(中 + 1, 比);
返回节点;
}
公共无效inorderTraversal(节点节点) {

如果(根== NULL){
的System.out.println(“树是空的”);
回报;
}
其他 {

如果(node.left!= NULL)
inorderTraversal(node.left);
是System.out.print(node.data + ” “);
如果(node.right!= NULL)
inorderTraversal(node.right);

}
}

公共静态无效的主要(串[] ARGS) {

ConvertBTtoBST BT =新ConvertBTtoBST();
INT ARR[] = { 10, 2, 7,8, 4 };
bt.root = bt.insertLevelOrder(ARR, bt.root, 0);
bt.inOrder(bt.root);
节点BST = bt.convertBTBST(bt.root);
的System.out.println(“\导致二叉搜索树的nInorder表示: “);
bt.inorderTraversal(BST);
}
}

回复
油漆说:

十二月 14, 2019 在 10:39 是

向你致敬
我仍然不太清楚计算方法，您能解释一下什么？
假设如果 1 if算法 (ñ <= 0) 是否有可能计算出这种复杂性

回复
阮天安 说:

四月 15, 2020 在 10:05 是

1. 为 (我= 1;在<= N;我 )
2. 为 (u = 1;在<= M;你++)
3. 为 (v = 1;在<= N;v ++)
4. //命令
5. 为 (j = 1;Ĵ<= X;J )
6. 为 (k = 1;到<= z;ķ++)
7. //命令
帖子 1 出来多少
1. s = 1; p = 1;
2. 为 (I = 1;在<= N;我 ) {
3. p = p * X / 在;
4. S =小号 + P;
5. }
帖子 2 您的结果是如此

令整数序列包含不同的单数. 第一个元素的位置约定是 0. 在序列a或输出中找到值为k的元素的位置 -1 如果没有等于k的元素.
从文件TIMKIEM.INP输入的数据具有以下形式:
– 第一行是整数n和k
– 第二行包含n个数字
输出文件TIMKIEM.OUT具有以下形式: k在序列中的位置.
建议:
– 使用数组 1 尺寸将元素保存在第th行 2 在文件.
– 建立递归算法以查找数组中的k.

例:
TIMKIEM.INP
6 8
9 2 8 3 1 4
TIMKIEM.OUT
2
您如何解决本文中的代码？

回复
何氏清化 说:

六月 4, 2020 在 1:57 下午

计算由以下函数实现的算法的时间复杂度:
我(INTñ){
如果 (n == 0) 回报 0;
否则返回n + 总和(N-1);
}
我问老师，这篇文章有多少复杂性?

回复