算法与设计

### 知识点一：程序性能的基本概念 **程序性能**是衡量软件系统运行效率的重要指标，主要包括**空间复杂度**和**时间复杂度**两个方面。空间复杂度指的是程序执行过程中所需内存空间的大小，而时间复杂度则是指程序执行所需时间的长短。 #### 1.1 性能评估的组成部分 - **性能分析（Performance Analysis）**：通过理论分析预测程序的性能表现。 - **性能测量（Performance Measurement）**：通过实际测试获取程序的性能数据。 ### 知识点二：考虑复杂性的理由 **空间复杂性**： - 在多用户系统中，需要为每个程序分配一定的内存空间。 - 需要预估系统是否有足够的内存来支持程序运行。 - 对于同一问题，可能有多种解决方案，需要对比它们在内存使用上的优劣。 - 通过空间复杂性评估程序能处理的最大问题规模。 **时间复杂性**： - 某些应用场合需要保证程序的响应时间在可接受范围内。 - 开发过程中需要确保程序能满足实时响应的需求。 ### 知识点三：方案选取原则 - 当存在多种解决问题的方案时，应当根据它们之间的时间和空间复杂度差异进行选择。 - 在实际操作中，通常更重视时间复杂度而非空间复杂度，因为现代计算机系统的内存资源相对充足。 ### 知识点四：空间复杂性的分类 #### 4.1 程序所需空间的主要组成部分 - **指令空间**：用于存储程序指令。其大小受到编译器的选择、编译选项及目标计算机配置的影响。 - **数据空间**：用于存储程序中的所有变量和常量值。 - 常量和简单变量所需的空间取决于计算机配置和编译器设置。 - 复合变量（如数组、结构体等）所需的空间则由其内部成员的总和决定。 - **环境栈空间**：用于保存函数调用期间需要的信息（如返回地址、局部变量等）。 ### 知识点五：数据空间的计算方法 - **简单变量**：空间需求取决于变量类型及数量。 - **复合变量**： - 结构体变量所占空间为其各成员变量占用空间之和。 - 数组变量所占空间为其数组大小乘以单个元素占用的空间大小。 - **实例特征**：决定问题规模的因素，如排序问题中的元素数量等。 ### 知识点六：环境栈空间的特点 - 主要用于存储函数调用过程中的信息，包括返回地址、局部变量和参数等。 - 其大小取决于局部变量及参数所需空间，以及递归调用的最大深度。 ### 知识点七：程序空间复杂性的组成 - 程序所需空间可以分为**固定部分**和**变化部分**。 - **固定部分**包括指令空间、常量及简单变量的数据空间等，不随问题规模变化。 - **变化部分**主要是与问题规模相关的数据空间和环境栈空间。 理解程序的性能表现尤其是空间复杂性和时间复杂性是非常重要的，它不仅有助于优化程序设计，还能帮助开发者在多种解决方案中做出最佳选择。同时，合理管理程序的空间使用情况也能提高程序的整体效率，减少不必要的资源浪费。