/*
    问题：给定一个整数 n，编程求解 1 + 2 + 3 + ... + n 的和。
*/
#include <iostream>

using namespace std;

long sum1(int n)
{
    long ret = 0;
    int* array = new int[n];
    
    for(int i=0; i<n; i++)
    {
        array[i] = i + 1;
    }
    
    for(int i=0; i<n; i++)
    {
        ret += array[i];
    }
    
    delete[] array;
    
    return ret;
}

long sum2(int n)
{
    long ret = 0;
    
    for(int i=1; i<=n; i++)
    {
        ret += i;
    }
    
    return ret;
}

long sum3(int n)
{
    long ret = 0;
    
    if( n > 0 )
    {
        ret = (1 + n) * n / 2;
    }
    
    return ret;
}

int main()
{
    cout << "sum1(100) = " << sum1(100) << endl;
    cout << "sum2(100) = " << sum2(100) << endl;
    cout << "sum3(100) = " << sum3(100) << endl;
    
    return 0;
}

5、程序评鉴初探

用尽量少的时间解决问题
用尽量少的步骤解决问题
用尽量少的内存解决问题

优秀的开发者追求高质量的代码！

6、数据结构课程的历史起源

1968年，由高纳德教授(Donald E.Knuth )开创一同年，在计算机科学的学位课程中出现（必修）

7、数据结构课程的研究范围

非数值计算类型的程序问题
数据间的组织和操作方式
数据的逻辑结构和存储结构

8、历史上的经典公式

程序 = 数据结构＋算法

对于数据结构和算法的研究，语言不重要，重要的是思想。

9、小结

程序是为了解决实际问题而存在的
针对同一个问题可以有多种解决方案
专业程序员应该尽量追求高质量的程序
数据结构课程主要研究非数值计算问题

二、数据的艺术

1、程序设计的挑战

利用计算机解决现实生活中的问题
生活中的不同个体间存在联系
用计算机程序描述生活中个体间的联系

2、问题

如何用程序描述生活中的个体？

3、数据的艺术

数据的概念
程序的操作对象，用于描述客观事物
数据的特点
可以输入到计算机
可以被计算机程序处理

4、数据中的新概念

数据元素
组成数据的基本单位
数据项
一个数据元素由若干数据项组成
数据对象
性质相同的数据元素的集合

5、数据实例分析

6、数据结构指数据对象中数据元素之间的关系

数据元素之间不是独立的
存在特定的关系，这些关系即结构
如：
数组中各个元素之间存在固定的线性关系

编写一个“好”的程序之前，必须分析待处理问题中各个对象的特性，以及对象之间的关系。

7、逻辑结构

集合结构
数据元素之间没有特别的关系，仅同属相同集合
线性结构
数据元素之间是一对一的关系
树形结构
数据元素之间存在一对多的层次关系
图形结构
数据元素之间是多对多的关系

8、物理结构

逻辑结构在计算机中的存储形式
顺序存储结构
将数据存储在地址连续的存储单元里
链式存储结构
将数据存储在任意的存储单元里
通过保存地址的方式找到相关联的数据元素

9、数据的艺术

数据结构是相互之间存在特定关系的数据元素的集合
数据结构可以分为逻辑结构和物理结构

三、初识程序的灵魂

1、初识程序的灵魂

数据结构静态的描述了数据元素之间的关系
高效的程序需要在数据结构的基础上设计和选择算法
算法是特定问题求解步骤的描述
在计算机中表现为指令的有限序列

2、算法的特性

输入：算法具有0个或多个输入
输出：算法至少有1个或多个输出
有穷性：算法在有限的步骤之后会自动结束而不会无限循环
确定性︰算法中的每一步都有确定的含义，不会出现二义性
可行性：算法的每一步都是可行的
正确性
算法对于合法数据能够得到满足要求的结果
算法能够处理非法输入，并得到合理的结果
算法对于边界数据和压力数据都能得到满足要求的结果
注意：正确性是算法最需要满足的基本的准则，但是作为计算机程序，不可能无限制的满足这条准则。
可读性
算法要方便阅读，理解和交流

注意：算法可读性是最容易被忽视的，然而，程序是写给人看的，而不是计算机。

健壮性
算法不应该产生莫名其妙的结果
性价比
利用最少的资源得到满足要求的结果

3、小结

算法为了解决实际问题而存在
数据结构是算法处理问题的载体
数据结构与算法相辅相成，共同解决问题

四、程序灵魂的审判

1、木暮的思考。。。

如果两个算法都满足功能性需求，那工程中最关心的其它特性是什么？如何比较评判呢？

注意：

性价比（效率）是工程中最已关注的算法附加特性！

2、算法效率的度量

事后统计法
比较不同算法对同一组输入数据的运行处理时间
缺陷
为了获得不同算法的运行时间必须编写相应程序
运行时间严重依赖硬件以及运行时的环境因素
算法的测试数据的选取相当困难
事前分析估算
依据统计的方法对算法效率进行估算
影响算法效率的主要因素

1. 算法采用的策略和方法

2. 问题的输入规模

3. 编译器所产生的代码

4. 计算机执行速度

算法效率的简单估算一
算法效率的简单估算二
算法效率的简单估算三

3、实例分析：程序效率估算

#include <iostream>

using namespace std;

int func(int a[], int len)       // ==> (n*n + 2)
{
    int ret = 0;      // 1
    
    for(int i=0; i<len; i++)     
    {
        for(int j=0; j<len; j++) 
        {
            ret += a[i] * a[j];  // n * n
        }
    }
    
    return ret;      // 1
}

int main()
{
    int array[] = {1, 2, 3, 4, 5};
    
    cout << func(array, 5) << endl;
    
    return 0;
}

4、程序灵魂的审判

启示
程序效率估算练习中的关键部分的操作数量为n*n
三种求和算法中关键部分的操作数量分别为2n, n和1
随着问题规模n的增大，它们操作数量的差异会越来越大，因此实际算法在效率上的差异也会变得非常明显！
算法操作数量的对比一
算法操作数量的对比二
算法操作数量的对比三

5、小结

算法的度量有事后统计法和事前分析估算法
事后统计法不容易准确度量算法的效率
事前分析估算法通过操作数量度量算法效率
判断一个算法效率时只需要已关注最高阶项就能得出结论
某个算法，随着问题规模n的增大，它会越来越优于另一算法，或者越来越差于另一算法。

五、算法的时间复杂度

1、结论

判断一个算法的效率时，操作数量中的常数项和其他次要项常常可以忽略，只需要已关注最高阶项就能得出结论。

2、问题

如何用符号定性的判断算法的效率？

3、算法的复杂度

时间复杂度
算法运行后对时间需求量的定性描述
空间复杂度
算法运行后对空间需求量的定性描述

注意！！！

数据结构课程重点已关注的是算法的效率问题，因此，整个课程会集中于讨论算法的时间复杂度；

但其使用的方法完全可以用于空间复杂度的判断！

4、大O表示法

算法效率严重依赖于操作(Operation）数量
操作数量的估算可以作为时间复杂度的估算
在判断时首先已关注操作数量的最高次项

5、常见时间复杂度

线性阶时间复杂度：O(n)
对数阶时间复杂度：O(logn)
平方阶时间复杂度：O(n2)

6、时间复杂度计算练习

时间复杂度计算练习一

===> O(n^2)

时间复杂度计算练习二

此处子函数少个i++。

===> O(n^2)

时间复杂度计算练习三

===> O(n^3)

7、小结

时间复杂度是算法运行时对于时间的需求量
大O表示法用于描述算法的时间复杂度
大O表示法只已关注操作数量的最高次项
常见的时间复杂度为：线性阶，平方阶和对数阶

六、算法效率的度量

1、常见时间复杂度

2、常见时间复杂度的比较

3、算法分析示例

4、算法的最好与最坏情况

意义：

当算法在最坏情况下仍然能满足需求时，可以推断，算法的最好情况和平均情况都满足需求。

注意：

数据结构课程中，在没有特殊说明时，所分析算法的时间复杂度都是指最坏时间复杂度。

5、算法的空间复杂度（Space Complexity )

定义：S(n) = S(f(n))
n为算法的问题规模
f(n)为空间使用函数，与n相关
推导时间复杂度的方法同样适用于空间复杂度
例如：
当算法所需要的空间是常数时，空间复杂度为S(1)

6、空间复杂度计算练习

7、空间与时间的策略

多数情况下，算法的时间复杂度更令人已关注
如果有必要，可以通过增加额外空间降低时间复杂度
同理，也可以通过增加算法的耗时降低空间复杂度

8、实例分析：空间换时间

/*
    问题： 
    在一个由自然数1-1000中某些数字所组成的数组中，每个数字可能出现零次或者多次。
    设计一个算法，找出出现次数最多的数字。
*/

#include <iostream>

using namespace std;

void search(int a[], int len)     // O(n)
{
    int sp[1000] = {0};
    int max = 0;
    
    for(int i=0; i<len; i++)
    {
        sp[a[i] - 1]++;
    }
    
    for(int i=0; i<1000; i++)
    {
        if( max < sp[i] )
        {
            max = sp[i];
        }
    }
    
    for(int i=0; i<1000; i++)
    {
        if( max == sp[i] )
        {
            cout << i + 1 << endl;
        }
    }
}

int main(int argc, char* argv[])
{
    int a[] = {1, 1, 3, 4, 5, 6, 6, 6, 3, 3};
    
    search(a, sizeof(a)/sizeof(*a));

    return 0;
}