算法与设计

什么是算法？

算法就是解决问题的步骤和方法。

怎么评判一个算法的好坏？

评判算法好坏主要看两个核心指标：

1. 时间复杂度（运行速度）

• 定义：算法执行时间随输入规模增长的趋势
• 常见表示：大O记法 O(n), O(n²), O(log n)
• 理解：
  • O(1)：无论数据多少，时间都一样快（如数组按索引访问）
  • O(n)：数据增加1倍，时间也增加1倍（如线性查找）
  • O(n²)：数据增加1倍，时间增加4倍（如双重循环）
  • O(log n)：数据增加1倍，时间只增加一点（如二分查找）

2. 空间复杂度（内存消耗）

• 定义：算法执行过程中占用的内存空间
• 衡量标准：随着输入规模增长，额外需要的内存空间

3. 其他考虑因素

• 可读性：代码是否容易理解和维护
• 正确性：算法是否能得到正确结果
• 健壮性：是否能正确处理异常情况

Dijkstra算法知道吗？

Dijkstra算法用于计算带权有向图中从源顶点到所有其他顶点的最短路径。

算法核心

• 贪心策略：每次选择距离源点最近且未访问的顶点
• 适用范围：边权非负的图

算法步骤

1. 初始化：距离数组dist[]（源点为0，其他为∞），访问标记visited[]
2. 迭代过程：
   • 选择未访问顶点中距离最小的顶点u
   • 标记u为已访问
   • 更新u的所有邻居v的距离：dist[v] = min(dist[v], dist[u] + weight(u,v))
3. 重复直到所有顶点访问完毕

复杂度

• 时间复杂度：O(n²)（朴素实现），O(m log n)（优先队列优化）
• 空间复杂度：O(n)

局限性

• 不能处理负权边
• 只适用于单源最短路径

应用

• 地图导航
• 网络路由
• 物流路径规划