C++编程

函数和参数

传值参数(Value Parameters)

1. 形式参数: a, b, c

2. 实际参数: 3, x, y

3. 复制构造函数(copy constructor): 实参赋值给形参

4. 析构函数(destructor): 释放形式参数，不影响实参

模板函数(Template Functions)

• 函数模板: 针对仅参数类型不同的函数

• 类模板: 针对仅数据成员和成员函数类型不同的类

引用参数(Reference Parameters)

常量引用参数(Const Reference Parameters)

🥸 编程建议: 对于诸如 int、float 和 char 的简单数据类型，当函数不会修改实际参数值的时候我们可以采用传值参数 对于所有其他的数据类型（包括模板类型），当函数不会修改实际参数值的时候可以采用常量引用参数

返回值(Return Values)

• 值: 均被复制到环境中

• 引用: 为返回类型添加一个前缀&

• 常量引用: 一个不变化的对象

递归函数(Recursive Functions)

• 直接递归(direct recursion): 是指函数F的代码中直接包含了调用F的语句()

• 间接递归(indirect recursion): 是指函数F调用了函数G，G又调用了H，如此进行下去，直到F又被调用()

• 基本部分: 一般包含了的情况。此时是直接定义的(即非递归)

• 递归部分: 的参数必须有一个比n小

归纳证明

• 归纳初值

• 归纳假设

• 归纳步证明

1. 当  时，，显然成立

2. 假设对于  时成立，即：

3. 我们需要证明:
证毕

递归改为非递归

• 递归简洁、易编写、易懂

• 易证明正确性

• 改为非递归的目的是提高效率

• 单向递归可直接用迭代实现非递归

• 其他情形必须借助栈实现非递归(前期没学)

排列(Permutations)

定义:

• 表示n个元素的集合

• 为中移去以后所获得的集合

• 表示集合X中元素的排列方式

• 表示在中的每个排列方式的前面均加上以后所得到的排列方式

• 基本部分: n=1时，

• 递归部分: n>1时，

C++内存分配

4个内存区间如下:

• 栈: 在执行时需要的时候分配，在不需要的时候自动清除的变量存储区。里面的变量通常是局部变量、函数参数等

• 堆: 由new分配的内存块，他们要手动释放，一般一个new就要对应一个delete。如果程序员没有释放掉，那么在程序结束后，操作系统会自动回收

• 全局/静态存储区: 全局变量和静态(static)变量被分配到同一块内存中，他们共同占用这块内存区

• 常量存储区: 这是一块比较特殊的存储区，他们里面存放的是常量，不允许修改（当然，你也能通过非正当手段修改）

程序性能

空间复杂性

程序需要以下空间:

• 指令空间(Instruction space)

• 数据空间(Data space)

• 环境栈空间(Environment stack space)

空间复杂性度量

Examples

• 采用实例特征n来估算该函数的空间复杂性

• 假定T为int类型，则
数组a中的每个元素需要2个字节，
实参x，n需要2个字节，
局部变量i需要2个字节，
每个整型常量0和-1也分别需要2个字节

• 所以

• 因为该空间独立于n，所以

时间复杂性

• 一个程序P所占用的时间

• 编译时间与实例的特征无关。因此主要关注程序的运行时间。运行时间通常用“”来表示

寻找最大元素

多项式求值算法

计算排名

名次排序

名次排序优化(不移回)

选择排序

思想： 首先找出最大的元素，把它移动到a[n-1]，然后在余下的n-1个元素中寻找最大的元素并把它移动到a[n-2]，如此进行下去

冒泡排序

原理:

• 采用一种“冒泡策略”把最大元素移到右部。在冒泡过程中，对相邻的元素进行比较，如果左边的元素大于右边的元素，则交换这两个元素

• 在一次冒泡过程结束后，可以确信最大的元素肯定在最右边的位置上

顺序搜索

名次排序优化(原地重排)

名次排序存在的缺点？ 需要额外创建空间u[]

1. 从a[0] 开始，每次检查一个元素（r[i]为Rank）

2. 如果当前正在检查的元素为a[i] 且r[i]= i，那么可以跳过该元素，继续检查下一个元素

3. 如果r[i]≠i, 可以把a[i]与a[r[i]] 进行交换，交换的结果是把原a[i] 中的元素放到正确的排序位置r[i]上去。这种交换操作在位置i 处重复下去，直到应该排在位置i 处的元素被交换到位置i处

4. 之后，继续检查下一个位置

选择排序优化

• 缺点：即使元素已经按序排列，程序仍然继续运行

• 为了终止不必要的循环，在查找最大元素期间，可以顺便检查数组是否已按序排列

冒泡排序优化

插入排序

思想：因为只有一个元素的数组是一个有序数组，所以可以从包含n个元素的数组的第一个元素开始。 通过把第二个元素插入到这个单元数组中，可以得到一个大小为2的有序数组。 插入第三个元素可以得到一个大小为3的有序数组

排序算法比较

执行步数(Step Counts)

介绍:

• 利用操作计数方法来估算程序的时间复杂性忽略了所选择操作之外其他操作的开销

• 在统计执行步数的方法中，要统计程序/函数中所有部分的时间开销

• 与操作计数一样，执行步数也是实例特征的函数

程序步

介绍:

• 程序步可以定义为一个语法或语义意义上的程序片段，该片段的执行时间独立于实例特征

• 可以通过创建一个全局变量count 来确定一个程序或函数为完成其预定任务所需要的执行步数

• 把count引入到程序语句之中，每当原始程序或函数中的一条语句被执行时，就为count累加上该语句所需要的执行步数。当程序或函数运行结束时所得到的count的值即为所需要的执行步数

执行步数表

介绍

• 如果不想使用count计值语句，可以建立一张表，在该表中列出每条语句所需要的执行步数

• 建立这张表时，可以首先确定每条语句每一次执行所需要的步数以及该语句总的执行次数(即频率)，然后利用这两个量就可以得到每条语句总的执行步数，把所有语句的执行步数加在一起即可得到整个程序的执行步数

渐进符号

• Big Oh:

• Omega:

• Theta: (大写)

• Little Oh:

Big Oh

定义: 当且仅当存在正的常数和，使得对于所有的，有

• 加法规则

• 乘法规则

Omega

定义: 当且仅当存在正的常数和，使得对于所有的，有

Theta

定义: 当且仅当存在正常数和某个，使得对于所有的,有

Little Oh

定义 当且仅当 且

常用公式

和与积的引用规则

Examples

递推求和

递归求和

矩阵加法

矩阵转置

顺序搜索