算法设计与分析 课件 4.5-分治法 - 典型应用 - 二分有哪些信誉好的足球投注网站 - 平均时间复杂度分析.pptx

算法设计与分析

分治—二分有哪些信誉好的足球投注网站—平均时间复杂度分析

国家级实验教学示范中心计算机学科组规划教材算法设计与分析Python案例详解微课视频版

平均时间复杂度分析

分析输入种类

n+(n+1)=2n+1

确定每种输入出现的概率

假定每种输入出现的概率相等（这是平均时间复杂度分析的通常做法）

平均时间复杂度分析

确定不同输入需要的基本操作次数

1次比较

2次比较

3次比较

4次比较

5次比较

5次比较

平均时间复杂度分析

确定不同输入需要的基本操作次数

令St为需要比较t次的输入种类，有S1=1，S2=2，S3=4，S4=8，S5=48

平均时间复杂度分析

根据公式计算并化简

测试