分析算法控制结构分析算法控制结构|算法设计与

本文概述

for循环的复杂性
算法

要分析编程代码或算法, 我们必须注意到每条指令都会影响算法的整体性能, 因此, 必须单独分析每条指令以分析整体性能。但是, 每个编程代码中都有一些算法控制结构, 它们具有特定的渐近分析。
一些算法控制结构是：

排序
如果-然后-其他
for循环
While循环

1.排序：
假设我们的算法由A和B两部分组成。A花费时间tA, B花费时间tB进??行计算。总计算“ tA + tB”是根据顺序规则进行的。根据最大规则, 此计算时间为（max（tA, tB））。
例：

Suppose tA =O (n) and tB = θ (n2). Then, thetotal computation time can be calculated asComputation Time = tA + tB = (max (tA, tB) = (max (O (n), θ (n2)) = θ (n2)

2.如果-然后-其他：

文章图片
总时间的计算是根据条件规则“ if-then-else”进行的。根据最大规则, 此计算时间为max（tA, tB）。
例：

Suppose tA = O (n2) and tB = θ (n2) Calculate the total computation time for the following:Total Computation = (max (tA, tB)) = max (O (n2), θ (n2) = θ (n2)

3. For循环：
for循环的一般格式为：

For (initialization; condition; updation) { Statement(s); }

for循环的复杂性外循环执行N次。每次执行外循环时, 内循环执行M次。结果, 内部循环中的语句总共执行N * M次。因此, 两个循环的总复杂度为O（N2）
考虑以下循环：

for i ← 1 to n { P (i) }

如果（PI）的计算时间ti作为“ i”的函数而变化, 则用于循环的总计算时间不是通过乘法给出, 而是通过总和即。

For i ← 1 to n { P (i) }

需要
如果算法由嵌套的“ for”循环组成, 则总计算时间为

For i ← 1 to n { For j ←1 to n { P (ij) } }

例：
考虑以下“ for”循环, 计算以下内容的总计算时间：

For i ← 2 to n-1 { For j ← 3 to i { Sum ← Sum+A [i] [j] } }

解：
总计算时间为：

4. While循环：
分析循环的简单技术是确定所涉及变量的功能, 其值每次减小。其次, 要终止循环, 必须将值设为正整数。通过跟踪函数的值减少多少次, 可以获得循环的重复次数。分析“ while”循环的另一种方法是将它们视为递归算法。
算法

1. [Initialize] Set k: =1, LOC: =1 and MAX: = DATA [1] 2. Repeat steps 3 and 4 while K≤N 3.if MAX< DATA [k], then: Set LOC: = K and MAX: = DATA [k] 4. Set k: = k+1 [End of step 2 loop] 5. Write: LOC, MAX 6. EXIT

例：
计算n个整数数组中最大元素的算法数组Max的运行时间为O（n）。
解：