算法学习笔记（Hello算法）—— 初识算法

1、相关链接

Hello算法：Hello 算法 (hello-algo.com)

2、算法是什么

2.1 算法定义

算法是一系列明确、有限且有效的步骤或指令的集合，用于解决特定问题或执行特定任务。

算法具有以下基本特征：

• 输入：算法至少有一个输入（某些算法可能有多个输入），或者可以没有输入。
• 输出：算法必须至少产生一个输出，这个输出是解决问题的结果。
• 明确性：算法中的每一步都必须清晰无误，不能有歧义。
• 有限性：算法必须在有限的时间内完成，不能无限循环下去。
• 可行性：算法的每一步都应该是基本操作，可以被实际执行。

2.2 数据结构定义

数据结构（Data Structure）是计算机存储、组织数据的方式。它是计算机科学中的一个重要概念，主要目的是使数据的存储和访问更加高效、方便。数据结构根据其性质和用途，可以分为多种不同的类型。

不同数据元素之间不是独立的，而是存在特定的关系，我们将这些关系称为结构。

以下是数据结构的基本定义：

1. 数据对象的集合：数据结构是数据对象（或称为元素、值）的集合，这些对象可以是数字、字符、记录等。

2. 数据对象之间的关系：数据结构不仅包含数据对象，还包含数据对象之间的关系。这些关系定义了数据对象是如何组织和联系的。

3. 操作的集合：数据结构通常伴随着一系列预定义的操作，这些操作可以创建、修改、访问和删除数据结构中的数据。

数据结构的主要类型包括：

• 逻辑结构：这是从逻辑关系角度描述数据结构的，不考虑数据在计算机中的实际存储方式。常见的逻辑结构有：

  • 集合
  • 线性结构（如数组、链表、栈、队列）
  • 树形结构（如二叉树、多叉树、堆）
  • 图形结构（如无向图、有向图）

• 物理结构：这是数据结构在计算机中的实际存储方式，描述了数据的物理位置关系。常见的物理结构有：

  • 顺序存储结构：数据元素在内存中连续存放。
  • 链式存储结构：数据元素可以分散存储，通过指针连接。

数据结构的选择对算法的设计和程序的效率有着重要的影响。不同的数据结构适合解决不同类型的问题，例如：

• 数组适合随机访问，但不适合频繁的插入和删除操作。
• 链表适合频繁的插入和删除操作，但随机访问效率较低。
• 树和图结构适合表示具有层次或网状关系的数据。

2.3 数据结构和算法的关系

数据结构与算法之间有着紧密的关系，它们相辅相成，共同构成了计算机科学的核心内容。以下是数据结构与算法关系的几个方面：

算法依赖于数据结构：

• 算法的设计往往需要根据待处理数据的特性来选择合适的数据结构。例如，排序算法通常需要数组这种可以随机访问的数据结构，而图算法则需要用到图这种可以表示复杂关系的结构。
• 不同的数据结构可以影响算法的效率。例如，在链表和数组上实现排序算法，其时间和空间复杂度可能会有显著差异。

数据结构为算法提供服务：

• 数据结构提供了存储和管理数据的手段，使得算法能够高效地读取和修改数据。
• 数据结构封装了一些基本操作，如插入、删除、查找等，这些操作是算法实现的基础。

算法实现数据结构的操作：

• 数据结构定义了一组操作，而算法则是这些操作的实现。例如，链表数据结构定义了插入和删除操作，具体的插入和删除算法则决定了这些操作如何执行。

算法效率受数据结构影响：

• 数据结构的选择直接影响算法的性能。例如，哈希表提供了平均情况下常数时间的查找效率，而二叉搜索树则提供了对数时间的查找效率。
• 合适的数据结构可以降低算法的时间复杂度和空间复杂度。

2.4 其他定义

数据:是描述害观事物的符号，是计算机中可以操作的对象，是能被计算机识别，并输入给计算机处理的符号集合。数据不仅仅包括整型、实型等数值类型’还包括字符及声音、图像、视频等非数值类型。·

数据元素:是组成数据的、有一定意义的墓本单位，在计算机中通常作为整体处理，也被称为记录。

数据顶:—个数据元素可以由若干个数据顶组成。

比如人这样的数据元素，可以有眼睛、耳朵、鼻子、嘴巴、手、脚这些数据项，也可以有姓名、年龄、性别、家庭地址、联系电话、邮政编码等数据项，具体有哪些数据项，要由你做的系统来决定。

数据项是数据不可分割的最小单位。

数据对象:呈性质相同的数据元素的集合，是数据的子集。

2.算法复杂度分析

在算法设计中，我们先后追求以下两个层面的目标。

• 找到问题解法：算法需要在规定的输入范围内可靠地求得问题的正确解。
• 寻求最优解法：同一个问题可能存在多种解法，我们希望找到尽可能高效的算法。

算法效率已成为衡量算法优劣的主要评价指标，它包括以下两个维度。

• 时间效率：算法运行速度的快慢。 ‧
• 空间效率：算法占用内存空间的大小。

效率评估方法主要分为两种：实际测试、理论估算。

实际测试的优点和缺点

优点：

• 实际反映：实际测试可以在真实的硬件和软件环境下运行算法，能够反映出算法在实际使用中的性能，包括执行时间和内存消耗。
• 易于理解：测试结果通常以直观的数字形式呈现，易于非专业人士理解。
• 发现隐藏问题：在测试过程中可能会发现算法在实际应用中才会出现的隐藏问题，如并发执行时的竞态条件、内存泄漏等。
• 比较不同系统：通过在不同系统上进行测试，可以比较算法在不同环境下的表现。

缺点：

• 时间消耗：进行实际测试需要花费大量时间，特别是对于复杂算法和大数据集。
• 可能不全面：测试可能只覆盖了算法的部分功能或特定数据集，无法全面评估算法的性能。
• 环境依赖：测试结果受测试环境（如CPU、内存、操作系统等）的影响，可能不具有普遍性。
• 结果解释困难：有时候测试结果可能会因为外部因素（如系统负载）而出现波动，解释这些波动可能比较困难。

理论估算的优点和缺点

优点：

• 普适性：理论估算通常基于数学模型，可以在不考虑具体硬件和软件环境的情况下评估算法的性能。
• 预测性：理论分析可以帮助预测算法在不同规模数据上的表现，特别是在大数据集上。
• 成本低：与实际测试相比，理论估算通常不需要实际的硬件资源，成本较低。
• 指导意义：理论分析可以为算法改进提供方向，帮助开发者理解算法的局限性。

缺点：

• 抽象性：理论估算往往较为抽象，可能难以被非专业人士理解。
• 忽略实际因素：理论模型可能无法完全反映现实世界中的所有因素，如磁盘I/O、网络延迟等。
• 可能不准确：理论估算基于假设，如果这些假设与实际情况不符，估算结果可能不准确。
• 复杂度高：对于复杂算法，进行理论分析可能需要高级数学知识和复杂的推导过程。

总的来说，实际测试和理论估算是互补的。在实际应用中，通常会结合这两种方法来全面评估算法的效率。理论估算可以提供一个初步的指导，而实际测试则可以验证理论分析的结果，并发现实际应用中可能遇到的问题。

2.2 迭代与递归

两种基本的程序控制结构：迭代、递归。

2.2.1 迭代

迭代（Iteration）是一种在计算过程中重复执行一系列操作的方法或概念。在编程和算法设计中，迭代通常指的是通过循环结构来重复执行一段代码，直到满足某个终止条件。

• for循环：当知道迭代的次数时使用。

• while循环：当迭代的次数未知，但知道何时停止时使用。

• do-while循环（某些语言中）：至少执行一次循环体，然后根据条件决定是否继续迭代。

• 嵌套循环：在一个循环结构内嵌套另一个循环结构

public class Fibonacci {
 
    public static void main(String[] args) {
        int n = 10; // 例如，计算斐波那契数列的第10个数
        int result = fibonacciIterative(n);
        System.out.println("斐波那契数列的第" + n + "个数是: " + result);
    }
 
    // 迭代方法计算斐波那契数列
    public static int fibonacciIterative(int n) {
        if (n <= 1) {
            return n;
        }
        int fib = 1;
        int prevFib = 1;
 
        for (int i = 2; i < n; i++) {
            int temp = fib;
            fib += prevFib;
            prevFib = temp;
        }
        return fib;
    }
}

2.2.2 递归

递归（Recursion）是一种编程和算法设计中的技术，它涉及函数或方法调用自身以解决一个更小或更简单的问题。递归通常用于解决那些可以分解为相似子问题的问题。

递归的基本要素：

• 基线条件（Base Case）：这是递归终止的条件。基线条件是递归算法必须达到的一个简单情况，它可以直接解决而无需进一步递归。（终止条件：用于决定什么时候由“递”转“归”。）

• 递归步骤（Recursive Step）：这是算法中递归调用的部分，它将问题分解为更小的子问题。（返回结果：对应“归”，将当前递归层级的结果返回至上一层。）

• 递归调用（Recursive Call）：这是函数或方法调用自身的操作，通常输入更小或更简化的参数。

以下是一个使用递归在Java中计算阶乘的案例。阶乘是一个经典的递归问题，其中n!（n的阶乘）定义为n * (n-1) * (n-2) * ... * 1，并且0!被定义为1。

public class Factorial {
 
    // 递归方法计算阶乘
    public static int factorial(int n) {
        // 基线条件：如果n为0，返回1
        if (n == 0) {
            return 1;
        }
        // 递归步骤：n! = n * (n-1)!
        return n * factorial(n - 1);
    }
 
    public static void main(String[] args) {
        int number = 5; // 示例：计算5的阶乘
        int result = factorial(number);
        System.out.println(number + "! = " + result);
    }
}
 

迭代与递归可以得到相同的结果，但它们代表了两种完全不同的思考和解决问题的范式。

• 迭代：“自下而上”地解决问题。从最基础的步骤开始，然后不断重复或累加这些步骤，直到任务完成。
• 递归：“自上而下”地解决问题。将原问题分解为更小的子问题，这些子问题和原问题具有相同的形式。
• 迭代：在循环中模拟求和过程，从 1 遍历到 本文内容由网友自发贡献，转载请注明出处：【wpsshop博客】