查找算法时间复杂度表格

以下是常见查找算法的时间复杂度表格：

| 算法 | 平均时间复杂度 | 最坏时间复杂度 |
| --- | --- | --- |
| 线性查找 | O(n) | O(n) |
| 二分查找 | O(log n) | O(log n) |
| 哈希表查找 | O(1) | O(n) |

其中，线性查找是最简单的查找算法，它的时间复杂度是O(n)，即最坏情况下需要遍历整个数组才能找到目标元素。二分查找是一种更高效的算法，它的时间复杂度是O(log n)，即每次查找都可以将待查找区间缩小一半。哈希表查找是一种基于哈希函数的查找算法，它的平均时间复杂度是O(1)，但最坏情况下可能需要遍历整个哈希表，时间复杂度为O(n)。

相关问题

数据结构查找算法图解

数据结构中的查找算法是用于在特定的数据结构中寻找特定元素的过程。常见的查找算法有线性查找（顺序查找）和二分查找，还有更复杂的数据结构如哈希表和二叉搜索树（BST）中对应的查找方法。

1. **线性查找**（Sequential Search）：也叫顺序查找，是最基础的查找方法，从数组的第一个元素开始逐个比较，直到找到目标或遍历完整个数组。适用于小规模数组或者无序数组。

2. **二分查找**（Binary Search）：适用于已排序的数组，每次将搜索范围缩小一半，通过中间元素的比较决定是左半部分还是右半部分继续查找，大大提高了查找效率。

3. **哈希表查找**：使用哈希函数将键映射到存储位置，查找速度极快，平均时间复杂度为O(1)，但可能存在哈希冲突，需要解决冲突的方法。

4. **二叉搜索树查找**：对于每个节点，它的左子树所有节点值都小于该节点，右子树所有节点值都大于该节点。查找时从根节点开始，根据目标值与当前节点的大小关系决定左子树或右子树，直至找到目标或空树。

图解通常会用流程图、伪代码或实际的图形展示这些查找过程。例如，线性查找可以用一个箭头从第一个元素逐个指向下一个元素的示意图表示；二分查找则会展示递归调用的树形结构；哈希表可能会用一个表格和散列函数来展示键值对的存储和查找。

设计要求： （1）将全部航班信息录入到系统里。包括上面表格里的所有信息。 （2）自设不少于5名乘客的信息，并录入到系统里。乘客姓名可用张三、李四、小王、小明等，但不能使用字母和数字。 （3）设计一个查找算法，实现航班信息的快速查找。可使用线性比较查找、折半查找、二叉排序树（有加分）和哈希查找（有加分），需要分析算法的时间复杂度和查找成功及不成功时的平均查找长度。 （4）若一名乘客计划从哈尔滨到海口旅游，请为他设计一条最省钱的路径。可使用dijkstra算法。

好的，根据您的要求，我可以对航空订票系统进行一些完善和扩展。以下是具体实现方案：

### 航班信息管理模块

航班信息可以用一个 Flight 类来表示，该类包含上面表格中的所有字段。可以将航班信息存储在一个 Flight 数组中，也可以存储在数据库中。以下是 Flight 类的一个示例实现：

public class Flight {
    private int flight_id;
    private String departure_city;
    private String arrival_city;
    private String aircraft_type;
    private int member_quota;
    private int remaining_tickets;
    private float ticket_price;

    // 构造函数
    public Flight(int flight_id, String departure_city, String arrival_city, String aircraft_type,
                  int member_quota, int remaining_tickets, float ticket_price) {
        this.flight_id = flight_id;
        this.departure_city = departure_city;
        this.arrival_city = arrival_city;
        this.aircraft_type = aircraft_type;
        this.member_quota = member_quota;
        this.remaining_tickets = remaining_tickets;
        this.ticket_price = ticket_price;
    }

    // getter 和 setter 方法
    // ...
}

然后，在程序中实现以下功能：

1. 添加航班信息。用户输入所有必要的信息，创建一个 Flight 对象，并将其添加到 Flight 数组或数据库中。

2. 修改航班信息。用户输入要修改的航班号和修改后的信息，查找对应的 Flight 对象，并更新其字段。

3. 删除航班信息。用户输入要删除的航班号，查找对应的 Flight 对象，并将其从 Flight 数组或数据库中删除。

4. 查找航班信息。实现查找算法，用户输入出发城市和到达城市，程序会在 Flight 数组或数据库中查找符合条件的航班信息，并将结果展示给用户。

以下是可能的查找算法的实现：

* 线性比较查找：遍历整个 Flight 数组，依次比较每个元素的出发城市和到达城市，并返回符合条件的航班信息。时间复杂度为 O(n)，平均查找长度为 n/2。
* 折半查找：要求 Flight 数组按照航班号有序排列。从数组的中间位置开始，依次比较航班号，如果要查找的航班号小于中间位置的航班号，则在数组的左半部分继续查找，否则在右半部分继续查找，直到找到符合条件的航班信息或者查找区间为空。时间复杂度为 O(log n)，平均查找长度为 (log n + 1) / 2。
* 二叉排序树：将 Flight 对象插入到一棵二叉排序树中，树的每个节点包含一个 Flight 对象和两个子节点，左子节点的航班号小于该节点的航班号，右子节点的航班号大于该节点的航班号。查找时，从根节点开始，依次比较航班号，如果要查找的航班号小于当前节点的航班号，则在左子树中继续查找，否则在右子树中继续查找，直到找到符合条件的节点或者查找到叶子节点。时间复杂度为 O(log n)，平均查找长度取决于树的形态，可以通过平衡二叉树等方式来优化。
* 哈希查找：将 Flight 对象插入到一个哈希表中，哈希表的每个桶包含一个 Flight 对象的链表。查找时，先根据出发城市和到达城市计算哈希值，然后在对应的桶中查找符合条件的航班信息。时间复杂度为 O(1)，平均查找长度取决于哈希函数的设计和哈希表的负载因子。

### 乘客信息管理模块

乘客信息可以用一个 Passenger 类来表示，该类包含乘客姓名、航班号、乘机日期和订票数量等字段。可以将乘客信息存储在一个 Passenger 数组中，也可以存储在数据库中。以下是 Passenger 类的一个示例实现：

public class Passenger {
    private String name;
    private int flight_id;
    private LocalDate flight_date;
    private int ticket_count;

    // 构造函数
    public Passenger(String name, int flight_id, LocalDate flight_date, int ticket_count) {
        this.name = name;
        this.flight_id = flight_id;
        this.flight_date = flight_date;
        this.ticket_count = ticket_count;
    }

    // getter 和 setter 方法
    // ...
}

然后，在程序中实现以下功能：

1. 添加乘客信息。用户输入所有必要的信息，创建一个 Passenger 对象，并将其添加到 Passenger 数组或数据库中。

2. 修改乘客信息。用户输入要修改的乘客姓名和修改后的信息，查找对应的 Passenger 对象，并更新其字段。

3. 删除乘客信息。用户输入要删除的乘客姓名，查找对应的 Passenger 对象，并将其从 Passenger 数组或数据库中删除。

4. 查找乘客信息。用户输入乘客姓名，程序会在 Passenger 数组或数据库中查找符合条件的乘客信息，并将结果展示给用户。

5. 订票。用户输入航班号和订票数量，程序会检查该航班是否有足够的余票，如果有，则在 Passenger 数组或数据库中添加一条记录，并更新航班信息表中的剩余票量。

6. 退票。用户输入乘客姓名，程序会删除 Passenger 数组或数据库中对应的记录，并更新航班信息表中的剩余票量。

7. 查询航班余票。用户输入航班号，程序会查询航班信息表中对应航班的剩余票量，并将结果展示给用户。

### 最省钱的路径算法

最省钱的路径算法可以使用 Dijkstra 算法，该算法可以在有向带权图中找到单源最短路径。以下是 Dijkstra 算法的实现步骤：

1. 初始化。将起点的距离设为 0，将其他点的距离设为无穷大。

2. 遍历所有点。从未标记的点中选取距离起点最近的点，将其标记为已访问，并更新与该点相邻的未标记点的距离。

3. 终止条件。如果所有点都已标记，或者没有未标记的点与起点相连，则算法终止。

4. 输出结果。最短路径就是从起点到终点的路径，并且经过的所有点的距离之和最小。

以下是可能的 Dijkstra 算法的实现：

public class Dijkstra {
    private int[][] graph; // 邻接矩阵表示的图
    private int start; // 起点
    private int[] dist; // 起点到各点的距离
    private boolean[] visited; // 是否已访问

    public Dijkstra(int[][] graph, int start) {
        this.graph = graph;
        this.start = start;

        int n = graph.length;
        this.dist = new int[n];
        this.visited = new boolean[n];

        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[start] = 0;
    }

    public void run() {
        for (int i = 0; i < graph.length; i++) {
            int u = -1;
            for (int j = 0; j < graph.length; j++) {
                if (!visited[j] && (u == -1 || dist[j] < dist[u])) {
                    u = j;
                }
            }
            visited[u] = true;
            for (int v = 0; v < graph.length; v++) {
                if (!visited[v] && graph[u][v] > 0 && dist[u] + graph[u][v] < dist[v]) {
                    dist[v] = dist[u] + graph[u][v];
                }
            }
        }
    }

    public int getDistance(int end) {
        return dist[end];
    }
}

其中，graph 是一个邻接矩阵，表示有向带权图，dist 是一个数组，表示起点到各点的距离，visited 是一个数组，表示各点是否已访问。可以将城市作为图中的节点，将航班价格作为边的权值，然后运行 Dijkstra 算法即可得到最省钱的路径。以下是可能的实现：

public class FlightGraph {
    private Map<String, Integer> cityIndexMap = new HashMap<>(); // 城市名称到节点编号的映射
    private List<String> cities = new ArrayList<>(); // 所有城市的列表
    private int[][] graph; // 邻接矩阵表示的图

    public