算法业计与分析 自底向上合并排序 ◆ while t<n ◆S←t:t←2s:i←0 while i+t<n merge(A, i+l, i+s,i+t AA◆i←-i+t end while ◆Ifi+s< n then merge(A,+1计+s,i+t) ◆ end while 21 算 分析
算法设计与分析 21 自底向上合并排序 w t ←1 w while t<n w s ←t; t ←2s; i ←0 w while i+t≤n w merge (A,i+1,i+s,i+t) w i ←i+t w end while w If i+s<n then merge (A,i+1,i+s,i+t) w end while
算法业计与分祈 nlogn 时 旧 n ogn 输入大小 22 算法设计与分析
算法设计与分析 22 n3 n2 nlogn nlogn 运行时间 输入大小
算法业计与分祈 时间复杂性 ◆定义1.1 计算总是以一个时间常量为上界 定义1.2 lim ≠∝ n→)0 g(n) f(n)=o(g(n)) ◆定义13 lim/(n) ≠0 n→0 8(n) f(n)=92(g(n) ◆定义14 f(n) C n→)0 g(n) f(n)=o(g(n)) 23 算法设计与分析
算法设计与分析 23 时间复杂性 w 定义1.1 计算总是以一个时间常量为上界 w 定义1.2 f(n) ＝O(g(n)) w 定义1.3 f(n) =Ω(g(n)) w 定义1.4 f(n)= Θ(g(n)) C ( ) ( ) lim g n f n n ( ) ( ) lim g n f n n 0 ( ) ( ) lim g n f n n
算法业计与分祈 S forj←2tos ifj划分 n then return false end for return true 24 算法设计与分析
算法设计与分析 24 s ← for j ←2 to s if j 划分n then return false end for return true n
算法业计与分祈 空间复杂性 S(n 空间耗费的度量方法通常定义为: 算法在运行时所占用内存单元的总数 即:存放数据的变量单元、程序代码、 工作变量、常数以及运行时的引用型 变量所占用的空间和递归栈空间的总和 举例说明 算法设计与分析
算法设计与分析 25 – S（n） – 空间耗费的度量方法通常定义为: 算法在运行时所占用内存单元的总数 即：存放数据的变量单元、程序代码、 工作变量、常数以及运行时的引用型 变量所占用的空间和递归栈空间的总和 举例说明 空间复杂性