目录
1--数据结构
2--算法
3--算法分析
4--实例1：普通算法与秦九韶算法的运算效率比较
5--实例2：最大子列和问题
5-1--暴力求解法
5-2--分而治之
5-3--动态规划
5-4--完整代码
1--数据结构
定义：所有数据元素以及数据元素之间的关系构成的集合；
数据结果一般包含以下方面：
数据的逻辑结构：由数据元素之间的逻辑关系构成；
数据的存储结构：即物理结构，表示数据元素及其关系在计算机存储器的存储表示；
数据的运算：表示施加在数据元素上的操作；
2--算法
定义：算法是对特定问题求解步骤的一种描述，其是指令的有限序列；
算法满足5个特性：有穷性、确定性、可行性、有输入、有输出；
3--算法分析
分析算法一般从时间复杂度和空间复杂度两方面进行评价与分析；
时间复杂度：
① 不同时间复杂度存在以下关系：O(1) < O(log n) < O(n) < O(n logn) < O(n^2) < O(2^n) < O(n!)；
空间复杂度：
① 定义：一个算法在运行过程中临时占用的存储空间大小；
4--实例1：普通算法与秦九韶算法的运算效率比较
实例代码：
#include <stdio.h>
#include <math.h>
#include <time.h>
#define MAXN 10
#define MAXK 1e7
clock_t start, stop;
double f1(int n, double a[], double x){
double p = a[0];
for(int i = 1; i <= n; i++){
p += (a[i] * pow(x, i));
}
return p;
}
double f2(int n, double a[], double x){
double p = a[n];
for(int i = n; i>0; i--){
p = a[i - 1] + x*p;
}
return p;
}
double cal_duration(int N, double *a, double x, int flag = 0){
double duration;
if (flag == 0){
start = clock();
for(int i = 0; i < MAXK; i++){
f1(N, a, x);
}
stop = clock();
}
else if(flag == 1){
start = clock();
for(int i = 0; i < MAXK; i++){
f2(N, a, x);
}
stop = clock();
}
// duration = ((double)(stop - start)) / CLK_TCK;
duration = ((double)(stop - start)) / CLOCKS_PER_SEC / MAXK; // Mac
return duration;
}
int main(int argc, char* argv[]){
// 存储多项式的系数
double a[MAXN];
for(int i = 0; i < MAXN; i++) a[i] = (double)i;
double x = 1.1;
double duration1 = cal_duration(MAXN - 1, a, x, 0); // f1计算
double duration2 = cal_duration(MAXN - 1, a, x, 1); // f2计算
printf("duration1 = %6.2e\n", duration1);
printf("duration1 = %6.2e\n", duration2);
return 0;
}运行结果：分析运行结果可知，秦九韶算法比普通算法的运算效率高一个数量级；
原因分析：
衡量算法效率一般采用时间复杂度进行比较；在上面的实例中，加减法的运算时间远低于乘除法，因此可以忽略；对于普通算法而言，其乘法的运算次数为 (1+2+……n) = (n^2 + n) / 2，即T(n) = C1*n^2 + C2*n；
对于秦九韶算法而言，其乘法的运算次数为 n，即T(n) = C1*n；
对比两个算法的T(n)，很明显普通算法的时间复杂度高于秦九韶算法；
5--实例2：最大子列和问题
问题描述：给定 N 个整数的序列{}，求解连续子序列和的最大值；
5-1--暴力求解法
方法①：
// Method1：暴力求解
int Method1(int *a, int N){
int Sum, MaxSum = 0;
for(int i = 0; i < N; i++){
for(int j = i; j < N; j++){
Sum = 0; // 计算所有子序列的和
for(int k = i; k <= j; k++){
Sum += a[k];
}
if(Sum > MaxSum) MaxSum = Sum;
}
}
return MaxSum;
}方法②：
// Method2：暴力求解
int Method2(int *a, int N){
int Sum, MaxSum = 0;
for(int i = 0; i < N; i++){
Sum = 0;
for(int j = i; j < N; j++){
Sum += a[j];
if(Sum > MaxSum) MaxSum = Sum;
}
}
return MaxSum;
}5-2--分而治之
// Method3：分而治之
int my_Max( int A, int B, int C ){
return A > B ? A > C ? A : C : B > C ? B : C;
}
int Method3(int *a, int left, int right){
int MaxLSum = 0, MaxRSum = 0;
int center, i;
int MaxLBSum = 0, MaxRBSum = 0;
int LBSum = 0, RBSum = 0;
if(left == right){ // 递归终止条件，子列只有一个数字
if(a[left] > 0) return a[left];
else return 0;
}
// 分
center = (left + right) / 2; // 分界线
// 递归求解左子列和右子列的最大和
MaxLSum = Method3(a, left, center);
MaxLSum = Method3(a, center+1, right);
// 求解跨分界线的最大子列和
// center -> left
for(i=center; i>=left; i--){
LBSum += a[i];
if(LBSum > MaxLBSum) MaxLBSum = LBSum;
}
// center -> right
for(i=center+1; i<=right; i++){
RBSum += a[i];
if(RBSum > MaxRBSum) MaxRBSum = RBSum;
}
// 治
return my_Max(MaxLSum, MaxRSum, MaxLBSum+MaxRBSum);
}5-3--动态规划
// Method4：在线处理
int Method4(int *a, int N){
int Sum = 0, MaxSum = 0;
for(int i = 0; i < N; i++){
Sum += a[i];
if(Sum > MaxSum){
MaxSum = Sum;
}
else if(Sum < 0){
Sum = 0;
}
}
return MaxSum;
}5-4--完整代码
#include "iostream"
#include <math.h>
class Cal_MaxSeqSum{
public:
Cal_MaxSeqSum(int *a, int N){
this -> a = a;
this -> N = N;
}
// Method1：暴力求解
int Method1(){
int Sum, MaxSum = 0;
for(int i = 0; i < this->N; i++){
for(int j = i; j < this->N; j++){
Sum = 0; // 计算所有子序列的和
for(int k = i; k <= j; k++){
Sum += this->a[k];
}
if(Sum > MaxSum) MaxSum = Sum;
}
}
return MaxSum;
}
// Method2：暴力求解
int Method2(){
int Sum, MaxSum = 0;
for(int i = 0; i < this->N; i++){
Sum = 0;
for(int j = i; j < this->N; j++){
Sum += this->a[j];
if(Sum > MaxSum) MaxSum = Sum;
}
}
return MaxSum;
}
// Method3：分而治之
int my_Max( int A, int B, int C ){
return A > B ? A > C ? A : C : B > C ? B : C;
}
int Method3(int *a, int left, int right){
int MaxLSum = 0, MaxRSum = 0;
int center, i;
int MaxLBSum = 0, MaxRBSum = 0;
int LBSum = 0, RBSum = 0;
if(left == right){ // 递归终止条件，子列只有一个数字
if(a[left] > 0) return a[left];
else return 0;
}
// 分
center = (left + right) / 2; // 分界线
// 递归求解左子列和右子列的最大和
MaxLSum = Method3(a, left, center);
MaxLSum = Method3(a, center+1, right);
// 求解跨分界线的最大子列和
// center -> left
for(i=center; i>=left; i--){
LBSum += a[i];
if(LBSum > MaxLBSum) MaxLBSum = LBSum;
}
// center -> right
for(i=center+1; i<=right; i++){
RBSum += a[i];
if(RBSum > MaxRBSum) MaxRBSum = RBSum;
}
// 治
return my_Max(MaxLSum, MaxRSum, MaxLBSum+MaxRBSum);
}
// Method4：在线处理
int Method4(){
int Sum = 0, MaxSum = 0;
for(int i = 0; i < this->N; i++){
Sum += this->a[i];
if(Sum > MaxSum){
MaxSum = Sum;
}
else if(Sum < 0){
Sum = 0;
}
}
return MaxSum;
}
int *a;
int N;
};
int main(int argc, char* argv[]){
// 初始化序列
int N = 8;
int seq[] = {4, -3, 5, -2, -1, 2, 6, -2};
Cal_MaxSeqSum cal(seq, N);
int sum1 = cal.Method1();
int sum2 = cal.Method2();
int sum3 = cal.Method3(seq, 0, N-1);
int sum4 = cal.Method4();
std::cout << "Sum1: " << sum1 << std::endl;
std::cout << "Sum2: " << sum2 << std::endl;
std::cout << "Sum3: " << sum3 << std::endl;
std::cout << "Sum4: " << sum4 << std::endl;
return 0;
}运行结果：
