> For the complete documentation index, see [llms.txt](https://cccs.viyi.cc/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://cccs.viyi.cc/2-cheng-xu-she-ji/2.4-suan-fa-ru-men-intro-to-algorithms.md).

# 2.4 算法入门（Intro to Algorithms）

## 2.4.1 概述

### 算法

算法（Algorithm）一词源自 1000 多年前的波斯博识者，阿尔·花拉子密(Abū ʿAbdallāh Muḥammad ibn Mūsā al-Khwārizmī), 代数（algebra）之父之一。

算法是指求解问题的具体步骤，一般来说所需步骤越短越好，但有时也会考虑占用内存的情况。

### 复杂度

算法的输入大小和运行步骤之间的关系叫做「算法复杂度」，使用「大 O 表示法」来衡量运行速度的量级。

## 2.4.2 选择排序（Selection sort）

遍历找到当前最小数，移动至最前，后从第二个继续循环该遍历，直到最后一个数字。算法时间复杂度为 ，指数级增长，效率较低。

![选择排序](/files/CUOdUaGScCNl6Y2NOp2L)

## 2.4.3 归并排序（merge sort）

若数组大小大于 1，则将数组对半分割，直至单个数组个数为 1（示例中）。接着从首个开始两两对比每组中第一个数字的大小，归并为 \* 2 个组，循环重复。

算法时间复杂度为 ，n 为比较 + 合并的次数（与输入成正比），log n 是合并步骤的次数（重复对半切是和输入呈对数关系）。

## 2.4.4 Dijkstra 算法

Dijkstra 是一种图搜索（graph search）算法，图由节点（node）和边（line）相连构成，点到点之间的代价称为成本（cost）或是权重（weight）。

若要计算任意某两点之间的最小代价路线，最简单的蛮力法是尝试每一条路计算总成本，时间复杂度为 ，阶乘量级是最糟糕的。

Dijkstra 算法是 Edsger Dijkstra 发明与 1956 年构思的算法，其[基本思想如下](https://www.bilibili.com/video/BV1EW411u7th?t=492.9\&p=13)：总是从代价最低的节点开始，运行一次后得知相邻节点的代价；再从相邻节点中的最小节点开始向前计算相邻节点的邻居的代价，更新该值，接着计算相邻节点中的第二小节点向前一步的代价，若相邻节点的同一邻居计算结果再次计算时比原值更小，则更新。

1956 年初始版本的 Dijkstra 算法的时间复杂度是 ，经改进后为 ，其中 n 为节点数，l 为边数。


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter, and the optional `goal` query parameter:

```
GET https://cccs.viyi.cc/2-cheng-xu-she-ji/2.4-suan-fa-ru-men-intro-to-algorithms.md?ask=<question>&goal=<endgoal>
```

`ask` is the immediate question: it should be specific, self-contained, and written in natural language.
`goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal.

The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.