算法原理复习提纲(3)

1. 如果用邻接表来表示E’&＃xff0c;为什么时间复杂度是O(|V|&＃43;|E|)&＃xff1f;&＃xff1f;
   我认为&＃xff0c;这是因为邻接表遍历一遍所有边需要O(|V|&＃43;|E|)&＃xff0c;这里要用顶点覆盖所有的边&＃xff0c;相当于把所有的边都遍历一遍
   
   
2. 时间复杂度如何计算&＃xff1f;&＃xff1f;
   U为点的集合&＃xff0c;U∩S确实需要时间O(|X|)&＃xff0c;因为要选择F中最大的S∩U&＃xff0c;所有有|F|个情况&＃xff0c;需要时间O(|X||F|)
   对于while循环&＃xff0c;直到U为空集&＃xff0c;最多|X|次循环&＃xff1b;并且每次选择|F|中的一个元素&＃xff0c;最多|F|次循环&＃xff0c;所有至多min(|X|,|F|)次循环
   
3. 这…顺序交叉如何实现的&＃xff1f;&＃xff1f;
   

1. 动态表装载因子&＃xff1a;表中存储的数据项的数量与表规模的比值

3.




4.
算法正确性&＃xff1a;对于每一个输入都最终停止并产生正确的输出结果算法正确性&＃xff1a;对于每一个输入都最终停止并产生正确的输出结果
随机算法&＃xff1a;对所有输入都停止&＃xff0c;可能产生错误解&＃xff0c;但与输入不相关&＃xff0c;且错误解的产生可控
近似算法&＃xff1a;对所有输入都停止&＃xff0c;对所有输入都产生近似正确的解

复杂度分析的目的&＃xff1a;预测算法对不同规模输入所需要的资源&＃xff0c;提供衡量算法优劣的测度手段&＃xff0c;为算法选择提供依据
渐进复杂度&＃xff1a;随着输入规模n的增加&＃xff0c;复杂度函数的增长趋势

• 快排序
  
• 归并排序&＃xff1a;分治法
• 插入排序
• 冒泡排序
• 基数排序