前言

本次知识想记录一下学习数据结构与算法分析中的知识：算法级数快速计算。

时间复杂度级数

分类

多项式级数

多项式级数，时间复杂度与多项式中最高次幂同级。例如：
$T(n)= a^2 + b + 2c^3 = O(n^3)$ 的时间复杂度:$O(n^3)$

指数级数(几何级数)

指数级，时间复杂度与其末项同阶。通向式：
$T(a^n) = a^0 + a^1 + … + a^n = O(a^n) $

算数级数

算数级数，时间复杂度与末项平方同阶。通向式：
$T(n) = 1 + 2 + 3 + … + n = O(n^2)$

幂方级数

幂方级数，时间复杂度，比幂次高出一阶。通项公式：
$T(n^2) = 1^2 + 2^2 + … + n^2 = O(n^3)$

收敛级数

收敛级数，时间复杂度近似$O(1)$。例如：
$\frac{1}{\frac{1}{2}} + \frac{1}{\frac{2}{3}} + … + \frac{1}{\frac{n-1}{n}} = O(1)$

调和级数

调和级数，时间复杂度的通项公式为：
$h(n) = 1 + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + … + \frac{1}{n} = ø(logn) $

对数级数

对数级数，时间复杂度的通项公式为：
$T(n) = log1 + log2 + … + log n = log(n!) <= O(n·logn)$

题目描述

Max Consecutive Ones
Given a binary array, find the maximum number of consecutive 1s in this array.

Example 1:

1
2
3
4

Input: [1,1,0,1,1,1]
Output: 3
Explanation: The first two digits or the last three digits are consecutive 1s.
    The maximum number of consecutive 1s is 3.

Note:

• The input array will only contain 0 and 1.
• The length of input array is a positive integer and will not exceed 10,000

这道题让我们求最大连续整数1的个数，难易程度为：简单。

方法

我们可以遍历一遍数组，用给一个计数器count来统计1的个数。如果遍历当前数字为0，那么count重置为0，如果不是0，count自增1，与全局result做max比较即可，时空复杂度分别为 $O(n)$ 和 $O(1)$ 参照以下代码：

Swift version :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

class Solution {
    func findMaxConsecutiveOnes(_ nums: [Int]) -> Int {
        var globalMax: Int = 0, localMax: Int = 0
        
        for num in nums {
            if num == 1 {
                localMax += 1
                globalMax = max(globalMax, localMax)
            } else {
                localMax = 0
            }
        }
        return globalMax
    }
}

C version :

1
2
3
4
5
6
7
8
9
10
11

int findMaxConsecutiveOnes(int* nums, int numsSize) {
    int globalMax = 0, localMax = 0;
    for(int i = 0; i < numsSize; i++) {
        if (nums[i] == 1) {
            globalMax = globalMax > ++localMax ? globalMax : localMax;
        } else {
            localMax = 0;
        }
    }
    return globalMax;
}

前言

来自：keshiim
链接：keshiim博客地址 https://keshiim.github.io

在程序设计中算法的性能分析是非常重要的，针对一个具体的问题可能提出若干种不同的算法实现。如何从这些算法中找出性能最有的那个？或者说是针对一个具体的算法如果评论它的优劣？这里要涉及的一个问题就是如何对算法的性能进行评价？评价算法性能主要充两个方面着手：

1. 算法的执行时间
2. 算法所有占中的存储空间

这两个指标分别对应算法的时间复杂度与空间复杂度，下面分别来说。

算法的时间复杂度

定义

算法的时间复杂度的目的是为了近似的评估算法的执行时间，因为要准确测量一个算法的执行时间多少是非常困难的，他收到计算机软硬件环境的影响。它的定义是这样的：
T(n) = O(f(n))
它表示随问题规模n的增大，算法的执行时间增长率和算法中语句的总体的执行次数f(n)增长率相同，称作算法的渐进时间复杂度，简称时间复杂度。其中这里的O来表示数量级，f(n)一般是算法中频度最大的语句频度。

如何求时间复杂度

要求算法的时间复杂度，关键就在于找到这个算法中执行频度最大的那条语句f(n)，找到了f(n)那么时间复杂度T(n)自然就出来了。
下面举例说明

1. 常数阶 $ O(1) $

1
2
3
4
5

void swap(int *i, int *j) {
    int temp = *i;
    *i = *j;
    *j = temp;
}

以上3条语句的语句频度都是1，而且该程序段的执行时间是一个与问题规模n无关的常熟。这种类型的算法的时间复杂度：T(n)=O(1)。

2. 线性形 $ O(n) $

1
2
3

for（int i = 0; i < n; i++) {
    //do you want to do.
}

很明显这种类型的算法的语句频度与问题的规模n刚好是呈线性相关的，时间复杂度为T(n)=O(n)。

3. 平方型 $ O(n^2) $

1
2
3
4
5
6
7
8
9
10

int[] a = {3, 2, 4, 7, ...., n};
for (int i = 0; i < n - 1; i++) {
    for (int j = i + 1; j < n; j++) {
        if (a[i] > a[j]) {
        //do swap, f(n)=n*n
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;   
    }
}

当有若干循环语句时，算法的时间复杂度是由嵌套最深的循环语句的频度f(n)决定。而忽略其他嵌套层次更低的循环。

4. 立方型 $ O(n^3) $

1
2
3
4

for i..n
    for ...
        for ...
            //do sth. //频度最大

常见的时间复杂度

$ O(1) $常熟型
$ O(\log2^{n}) $对数行
$ O(n\log2^{n}) $二维型
$ O(n) $线性型
$ O(n^2) $平方型
$ O(n^3) $立方型
$ O(2^n) $指数型

一般情况下，随问题规模n的增大，时间复杂度T(n)增长最慢的算法为最优算法。以上几种算法随n的不断增加时间复杂度增加越来越快，因此一般应该选择用O(nk)的算法。避免使用指数阶的算法。

最坏时间复杂度与平均时间复杂度

算法的时间复杂度不仅与问题规模n相关海域输入实例的初始状态有关。
看例子：

1
2
3

int i = n - 1;
while (i >= 0 && (a[i] != k))
    i--;

上述算法的时间复杂度不仅与n相关还与输入的数组a与k的取值相关：

1. 最坏情况：数组a中没有与k相等的元素。则语句3的频度f(n)=n，时间复杂度T(n)=O(n)
2. 最好情况：或a中最后一个元素等于k，则语句3的频度f(n)=0，时间复杂度T(n)=O(1)

一般不特别说明，讨论的时间复杂度均是最坏情况下的时间复杂度，这样做的原因是能够保证算法在任何输入实例情况下都能够被考虑到。而平均时间复杂度是指所有可能的输入实例均以等概率出现的情况下的时间复杂度，在这个例子中平均复杂度即为：O(1)

因此上述算法的时间复杂度为：O(n)

算法的控件复杂度

辅助存储空间

一般情况下，一个程序在机器上执行时，处理需要春初本身所需要的代码、输入数据外，还需要一些对数据金鑫操作的辅助存储空间。其中输入数据所占用的具体空间取决于问题本身，与算法无关。因此我们所讨论的空间发咋读只与改算法的实现时所需要的辅助空间单元个数相关。即 空间复杂度讨论的是算法所需要的辅助存储空间。

定义

算法的空间发咋读S(n)定义为该算法所耗费的存储空间的数量级，它是问题规模n的函数，记作：

S(n) = O(f(n))

若算法执行时间所需要的辅助空间相对于输入数据量而言是一个常数，则称这个算法为原地工作，负数空间为O(1)。看例子：

将一维数组a中的n个数据逆序存放到原数据中，下面是两种算法

算法1

1
2
3
4

for (i = 0; i < n; i++)
    b[i] = a[n - i - 1];
for (i = 0; i < n; i++)
    a[i] = b[i];

算法2

1
2
3
4
5

for (i = 0; i < n >> 2; i ++) {
    t = a[i];
    a[i] = a[n - i - 1];
    a[n - i - 1] = t;
}

• 算法1的空间复杂度为O(n)，需要一个大小为n的辅助数组b
• 算法2的空间复杂度为O(1)，仅需要一个变量t，与问题规模n无关

总结

算法的空间复杂度与时间复杂度合称为算法的复杂度。面对不同的算法如何选择主要就从这两个方面去考虑，理想情况是一个算法的时间与空间复杂度都小，但这是我很难做到的，面对不同的情况小具体问题具体分析：是以时间换空间，还是以空间换时间。

排序算法的性能比较(表)

Markdown 语法和 MWeb 写作使用说明

Markdown 的设计哲学

Markdown 的目標是實現「易讀易寫」。
不過最需要強調的便是它的可讀性。一份使用 Markdown 格式撰寫的文件應該可以直接以純文字發佈，並且看起來不會像是由許多標籤或是格式指令所構成。
Markdown 的語法有個主要的目的：用來作為一種網路內容的寫作用語言。

Farmer keshiim 将在这里播种阳光和希 望。· Jason Zheng