第一章 引论

1.本书讨论的内容

设有一组N个数而要确定其中第K个最大者，称之为选择问题

一种解法

该问题的一种解法是将这N个数读进一个数组中，再通过某种简单的算法，以递减顺序将数组排序，然后返回位置K上的元素

//冒泡排序
#include <iostream>
using namespace std;
int main()
{
    const int n = 10;
    const int k = 5;
    int arr[n];
    int i,j,t;

    for (i = 0; i < n; i++)
        cin >> arr[i];

    for (i = 0; i < n; i++)
    {
        for (j = 0; j < n-i-1; j++)
        {
            if (arr[j] < arr[j + 1])
            {
                t = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = t;
            }
        }
    }
    
    cout << arr[k - 1];

    return 0;
}

另一种解法

稍微好一点的算法可以先把前K个元素读入数组(并以递减的顺序)对其排序，接着，将剩下的元素再逐个读入。当新元素被读到时，如果它小于数组中的第K个元素则忽略，否则就将其放到数组中正确的位置上，同时将数组中的一个元素挤出数组，当算法终止时，位于第K个位置上的元素作为答案返回。

#include <iostream>
using namespace std;
int main()
{
    const int k = 15;

    int arr[k];
    int i, j, t;

    for (int i = 0; i < k; i++)
        cin >> arr[i];
    for (i = 0; i < k; i++)
    {
        for (j = 0; j < k-i-1; j++)
        {
            if (arr[j] < arr[j + 1])
            {
                t = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = t;
            }
        }
    }

    for (int i = 0; i < k; i++)                 //对K个值进行排序
    {
        cout << "arr[" << i << "] = ";
        cout << arr[i] << endl;
    }

    cout << "Enter \'q\' to quit" << endl;
    while(1)                                    //插入剩下的元素
    {
        int n;
        if (cin >> n)
        {
            for (i = 0; i < k; i++)
            {
                if (n > arr[i])
                {
                    for (j = k-1; j > i; j--)
                    {
                        arr[j] = arr[j-1];
                    }
                    arr[i] = n;
                    break;
                }

            }
         }
         else
             break;
    }

    for (int i = 0; i < k; i++)
    {
        cout << "arr[" << i << "] = ";
        cout << arr[i] << endl;
    }
}

虽然它们都能得出结果，但不认为是好的算法，在第七章内有另一种算法，对于第三种算法在合理的时间内能够处理的输入数据量而言，这两种算法是不切实际的。(Updating)
在许多问题当中，一个重要的观念是：写出一个可以工作的程序并不够。如果这个程序在巨大的数据集上运行，那么运行时间就变成了重要的问题。
如何估计程序的运行时间，尤其是如何在尚未具体编码的情况下比较两个程序的运行时间。彻底改进程序速度以及确定程序瓶颈的方法，使得我们能够找到大力优化的那些代码段。

2.数学知识复习

• 指数
• 对数
• 级数
• 模运算
• 证明方法
  ·归纳法 ·反证法

3.递归简论

当一个函数用它自己来定义时就称为是递归(recursive)的。

C提供的仅仅是遵循递归思想的一种企图，不是所有的数学递归函数都能有效的(或正确的)由C的递归模拟来实现。

F(0) = 0 且 F(X) = 2F(X-1) + X^2

#include <iostream>
using namespace std;
double F(double x)
{
    if (x == 0)                                  //处理基准情况
        return 0;
    if (x > 0)
        return 2 * F(x -1) + x * x;
}
int main()
{
    double x;
    cout << "Pleas input x: " << endl;
    cin >> x;
    cout << "F(x) = " << F(x) << endl;
    return 0;
}

F(X)函数中第一行和第二行处理基准情况(base case)，即此时函数的值可以直接算出而不用求助递归。C的递归函数若无基准情况，是毫无意义的。

递归的基本法则

• 1.基准情形(base case)
• 2.不断推进(making progress)
  对于那些需要递归求解的情形，递归调用必须总能够朝着产生基准情形的方向推进。
• 3.设计法则(design rule)
  假设所有的递归调用都能运行。
• 4.合成效益法则(compound interest rule)
  在求解一个问题的同一实例时，切勿在不同的递归调用中做重复性的工作。

4.总结

对于面对大量输入的算法，它所花费的时间是一个判别其好坏的重要标准。速度是相对的。