算法基础

高级提示词工程师| 第二部分：编程和算法

| 第三节：算法基础

| 知识点详解：

算法复杂度
- 时间复杂度：衡量算法执行时间的指标，通常与输入数据的规模有关。
- 空间复杂度：衡量算法在执行过程中占用存储空间的指标。
- 大O表示法：一种描述算法复杂度的符号，如O(n)表示线性时间复杂度。
排序算法
- 排序算法的目的是将一组数据按照特定顺序重新排列。
搜索算法
- 搜索算法用于在数据结构中查找特定元素。
递归
- 递归是一种通过函数自我调用实现问题分解的编程技巧。
图算法
- 图算法用于在图数据结构中遍历和搜索。
动态规划
- 动态规划是一种解决多阶段决策问题的方法，通过存储中间结果避免重复计算。
贪心算法
- 贪心算法在每一步选择局部最优解，以期望获得全局最优解。

代码示例与注释：

冒泡排序

function bubbleSort(arr) {
    var len = arr.length;
    for (var i = 0; i < len - 1; i++) {
        for (var j = 0; j < len - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) { // 相邻元素两两对比
                var temp = arr[j + 1]; // 元素交换
                arr[j + 1] = arr[j];
                arr[j] = temp;
            }
        }
    }
    return arr;
}
var arr = [6, 5, 4, 3, 2, 1];
console.log(arr); // [6, 5, 4, 3, 2, 1]
bubbleSort(arr);
console.log(arr); // [1, 2, 3, 4, 5, 6]

选择排序
选择排序示例

function selectionSort(arr) {
     if (arr == null || arr.length < 2) {
         return arr;
     }
     for (var i = 0; i < (arr.length - 1); i++) {
         let minIndex = i;
             for (let j = i + 1; j < arr.length; j++) {
                 minIndex = arr[j] < arr[minIndex] ? j : minIndex;
             }
         let temp = arr[i];
         arr[i] = arr[minIndex];
         arr[minIndex] = temp;
       }
     return arr;
  }
 var arr = [1, 3, 2, 8, 9, 1, 5];
 console.log(arr); // [1, 3, 2, 8, 9, 1, 5]
 selectionSort(arr);
 console.log(arr); // [1, 1, 2, 3, 5, 8, 9]

插入排序

插入排序示例

function insertionSort(arr) {
     if (arr == null || arr.length < 2) {
         return arr;
     }
     for (let i = 1; i < arr.length; i++) {
         for (let j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) {
             let temp = arr[j];
             arr[j] = arr[j + 1];
             arr[j + 1] = temp;
         }
     }
     return arr;
 }
 var arr = [3, 4, 2, 1, 6, 7, 8, 4];
 console.log(arr); // [3, 4, 2, 1, 6, 7, 8, 4]
 insertionSort(arr);
 console.log(arr); // [1, 2, 3, 4, 4, 6, 7, 8]

快速排序
快速排序示例

const quickSort = (array) => {
    const sort = (arr, left = 0, right = arr.length - 1) => {
        if (left >= right) { //如果左边的索引大于等于右边的索引说明整理完毕
            return
        }
        let i = left
        let j = right
        const baseVal = arr[j] // 取无序数组最后一个数为基准值
        while (i < j) { //把所有比基准值小的数放在左边大的数放在右边
            while (i < j && arr[i] <= baseVal) { //找到一个比基准值大的数交换
                i++
            }
        arr[j] = arr[i] // 将较大的值放在右边如果没有比基准值大的数就是将自己赋值给自己（i 等于 j）
            while (j > i && arr[j] >= baseVal) { //找到一个比基准值小的数交换
                j--
            }
        arr[i] = arr[j] // 将较小的值放在左边如果没有找到比基准值小的数就是将自己赋值给自己（i 等于 j）
      }
    arr[j] = baseVal // 将基准值放至中央位置完成一次循环（这时候 j 等于 i ）
    sort(arr, left, j - 1) // 将左边的无序数组重复上面的操作
    sort(arr, j + 1, right) // 将右边的无序数组重复上面的操作
    }
    const newArr = array.concat() // 为了保证这个函数是纯函数拷贝一次数组
    sort(newArr)
    return newArr
}
var arr = [6,5,4,5,3,4,1];
console.log(arr); // [6, 5, 4, 5, 3, 4, 1]
console.log(quickSort(arr)); // [1, 3, 4, 4, 5, 5, 6]

线性搜索

def linear_search(arr, x):
    # 遍历数组，查找目标值
    for i, item in enumerate(arr):
        # 如果找到目标值，返回当前索引
        if item == x:
            return i
    # 如果未找到，返回-1
    return -1

二分搜索

def binary_search(arr, x):
    # 初始化搜索区间的左右端点
    left, right = 0, len(arr) - 1
    while left <= right:
        # 计算中间位置
        mid = (left + right) // 2
        # 如果中间元素正好是目标值，返回中间位置
        if arr[mid] == x:
            return mid
        # 如果中间元素小于目标值，调整左边界
        elif arr[mid] < x:
            left = mid + 1
        # 如果中间元素大于目标值，调整右边界
        else:
            right = mid - 1
    # 如果搜索范围不存在目标值，返回-1
    return -1

递归示例：计算阶乘

def factorial(n):
    # 递归的终止条件，0的阶乘是1
    if n == 0:
        return 1
    # 递归调用，返回n乘以(n-1)的阶乘
    else:
        return n * factorial(n-1)

深度优先搜索（DFS）

def dfs(graph, start, visited=None):
    # 如果没有定义访问集合，则创建一个新的
    if visited is None:
        visited = set()
    # 标记起始顶点为已访问
    visited.add(start)
    # 打印当前访问的顶点
    print(start)
    # 递归访问当前顶点的所有未访问邻居
    for neighbour in graph[start] - visited:
        dfs(graph, neighbour, visited)

广度优先搜索（BFS）

from collections import deque

def bfs(graph, start):
    # 创建一个队列用于BFS
    queue = deque([start])
    # 创建一个集合用于记录已访问的顶点
    visited = set()
    while queue:
        # 从队列中取出一个顶点
        vertex = queue.popleft()
        # 如果该顶点还未访问，则访问并打印
        if vertex not in visited:
            visited.add(vertex)
            print(vertex)
            # 将该顶点的所有未访问邻居加入队列
            queue.extend(graph[vertex] - visited)

检验问题及详细解释：

问题一：编写冒泡排序算法的Python实现，并解释其工作原理和时间复杂度。
- 解答：冒泡排序通过重复遍历要排序的数列，比较每对相邻元素的大小，并在必要时交换它们的位置。这个过程重复进行，直到没有需要交换的元素为止，即数组已经排序完成。
- 时间复杂度：最坏情况下，冒泡排序的时间复杂度为O(n^2)，发生在每次比较都需要交换时。最佳情况下，如果数组已经排序，时间复杂度为O(n)。
问题二：实现快速排序算法，并解释其分治策略及时间复杂度。
- 解答：快速排序通过选取一个元素作为“基准”（pivot），然后将数组分为两个子数组，一个包含所有小于基准的元素，另一个包含所有大于基准的元素。这个过程称为分区（partitioning）。之后，递归地对这两个子数组进行快速排序。
- 时间复杂度：平均情况下，快速排序的时间复杂度为O(n log n)。最坏情况下，当选择的基准值是最小或最大元素时，时间复杂度为O(n^2)。
问题三：编写线性搜索算法的Python代码，并解释其适用场景。
- 解答：线性搜索通过遍历数组中的每个元素来查找特定值。如果找到匹配的元素，则返回该元素的索引；如果遍历完成后未找到，则返回-1或类似的表示未找到的值。
- 适用场景：线性搜索适用于小型数据集或无序数据集，且实现简单。
问题四：实现二分搜索算法，并解释为什么它要求数组是有序的，以及它的效率如何。
- 解答：二分搜索通过将目标值与数组中间元素进行比较，根据比较结果缩小搜索范围。如果目标值等于中间元素，则搜索成功；如果目标值小于中间元素，则在左半部分继续搜索；如果目标值大于中间元素，则在右半部分继续搜索。这个过程重复进行，直到找到目标值或搜索范围为空。
- 效率：二分搜索要求数组是有序的，这样每次比较后都能将搜索范围减半。二分搜索的时间复杂度为O(log n)，非常高效。
问题五：编写一个使用递归的算法，如阶乘或斐波那契数列，并解释递归的工作原理。
- 解答：递归算法通过函数自我调用来解决问题。例如，阶乘函数可以定义为n! = n * (n-1)!，当n为0时，0!定义为1。斐波那契数列可以定义为F(n) = F(n-1) + F(n-2)，其中F(0) = 0，F(1) = 1。
- 工作原理：递归算法将问题分解为更小的子问题，并使用相同的方法解决这些子问题。递归通常有一个或多个终止条件，以避免无限递归。
问题六：描述DFS和BFS算法的工作原理，并比较它们的不同及适用场景。
- 解答：DFS使用栈（可以是显式的栈或隐式的函数调用栈）来遍历图或树的深度，尽可能深地搜索分支。BFS使用队列来遍历图或树的广度，一层一层地访问节点。
- 不同：DFS适用于寻找路径或连通性问题，而BFS适用于寻找最短路径问题。
问题七：实现一个动态规划算法解决实际问题，如背包问题或最长公共子序列，并解释动态规划的优势。
- 解答：动态规划通过将问题分解为重叠子问题，并存储这些子问题的解（通常是在表格中），避免重复计算。例如，背包问题可以通过动态规划来解决，其中每个子问题表示在不超过背包容量的前提下，选择物品的组合方式。
- 优势：动态规划避免了递归算法中的重复计算，通常能显著提高问题求解的效率。
问题八：解释贪心算法的工作原理，并给出一个使用贪心算法解决的问题示例，如硬币找零或任务调度。
- 解答：贪心算法在每一步选择当前看起来最优的选择，以期望这样的选择能导致全局最优解。例如，在硬币找零问题中，贪心算法会优先使用最大面额的硬币来减少硬币的总数。
- 工作原理：贪心算法不保证总能得到全局最优解，但在某些问题上，如单源最短路径问题，贪心选择能产生最优解。
问题九：讨论算法复杂度分析的重要性，并给出一个分析示例，说明如何评估算法的效率。
- 解答：算法复杂度分析是评估算法效率的重要工具。它帮助我们理解和比较不同算法在不同输入规模下的性能。例如，对于排序算法，我们可以通过比较它们的时间复杂度来评估效率。
问题十：实现一个你认为比冒泡排序更高效的排序算法，并证明其时间复杂度更低。
- 解答：快速排序、归并排序或堆排序通常比冒泡排序更高效。例如，归并排序通过分治法将数组分成两半，递归排序后再合并，其时间复杂度为O(n log n)，比冒泡排序的O(n^2)要低。

通过详细解答这些问题，你将能够检验自己对算法基础知识的掌握程度，并加深对不同算法性能和适用性的理解。

高级提示词工程师 > 学习方案 > 2.编程和算法

#高级提示词工程师 #编程和算法

算法基础

http://example.com/2024/06/21/关卡3：算法基础/

Beitragsautor

XiaoXiangHui

Veröffentlicht am

June 21, 2024

Urheberrechtshinweis

面向对象编程 Vorheriger

数据结构基础 Nächster