course_data_structures/Data Structure Class 1/hw1/192181-30+雷宇辰+作业1

Value:
void Fib::Value(const int &n) //计算并设置斐波那契数列第n项的值value
{
    int a = 0, b = 1;
    for (int i = 0; i < n; i++)
    {
        int t = a + b;
        a = b, b = t;
    }
    value = a;
}
时间复杂度O(n),空间复杂度O(1)。
有基于矩阵快速幂的O(logn)做法，
然而在结果在int范围内的情况下常数较大，
这里不列出了。

Partition:
int Partition(int x[], int n, int &movenum, int &compnum, int &bytesnum)
{
    bytesnum = 2 * sizeof(int);
    int i = 0;
    for (int j = 1; j < n; j++)
    {
        compnum++;
        if (x[j] < x[0])
            swap(x, ++i, j), movenum += 3;
    }
    swap(x, 0, i), movenum += 3;
    return i;
}
时间复杂度O(n),空间复杂度O(1)。
将整个数组就地分成大于x[0]和小于x[0]的两部分。