说一下数据结构与算法(三)

枕上十年事，江南二老忧，都到心头。

上篇文章中介绍，算法的好坏主要是看完成这个步骤所需要的步数.比如说在

有序数组中插入的效率低，但是查找却很快

常规数组中插入的效率高，反之查找却很慢

当我们在记录这个算法的步骤的时候,不能写出“一个长度为N的有序数组中用二分查找需要的步骤为XX步”.这样写不仅浪费时间又啰嗦，这是我们不想要的，那么有什么办法简洁明了的表示算法的步数的呢?

大O记法

大O记法用来表示操作数据的算法时间复杂度,这里需要多说一句，虽然名字叫”时间复杂度”但是这里所说的并不代表时间,指的仍旧是操作的步数.为什么呢?因为在不同硬件配置的电脑上,运行同一段代码肯定会出现时间差,一个快一点一个慢一点.但是它们运行代码的步骤是不会变的,假如在A电脑上运行的速度为a,在B电脑上运行的速度为b.已知a>b.运行一个长度为N的数组线性查找,我们知道,步数是N,那么,算时间就是a*N必然大于b*N.同一段代码在2台电脑上有不同的运行时间(这里的时间指的是实际时间).但是这个时间差对与算法本身并没有参考价值.所以,虽然叫时间复杂度,但是指的还是步数的多少.

第一篇介绍数据结构的文章中说过:在数组中做读取操作,不管数组有多长,程序只会运行一步,因为数组中的元素都有下标,根据下标能很快的找到对应的元素.
所以,用大O记法表示的话应该是

O(1) 读作”大O1″

那么如果一个操作,同样的不管数组多次,程序都要运行2次才能完成,那么这样的是不是就要记作O(2)了呢?然而并不是.记录算法的时间复杂度依然是O(1).这个1代表的是一个常量,即不管数据的大小,程序运行的步骤总是恒定的.这样的统一记作O(1).

O(1)也称之为常数时间

有一点值得要说明的是:大O记法记录的总是最坏的情况,这样一来最坏情况与最优情况就会表现的不同.所以我们做一个约定,如果没有特殊说明,大O记法表示的总是最坏情况.

如果一个操作是随着数据的增加增加的,比如在长度为N的有序数组中插入大于当前最大值的数,首先程序会比较N次,然后再将数字插入到数组的最后.那么时间复杂度应该为N+1.用大O记法应该是O(N).即代表算法的时间复杂度随着数据的增长而增长,它们之间存在着对应着的关系.所以这样的时间复杂度统一记作O(N).

O(N)也称之为线性时间

那么,上篇文章中提到的第一个算法,二分查找用大O记法该怎么表示呢?它既不是常数时间也不是线性时间,不知道还记不记得,二分查找是长度没增加一倍,它的步数增加1步.这一看就很有规律.

比如

查找2步的有序数组长度是5,

查找3步的有序数组长度是9,

查找4步的有序数组长度是17

…

(注:因为好找中间数,所以数组的长度都加了1)

画出的图应该是下面的样子

显然是对数函数,所以二分查找的时间复杂度的写法应该是O(lon2N),但是一般为了简写都写作O(lonN).

O(logN)称之为对数时间

延申

其实到了上面,完全可以进行下一文章的书写了,但是为了照顾一些学的比较好的,或者想多了解几种算法的时间复杂度与具体的时间复杂度计算方法的人.所以写下下面的延申.

我的写的代码是已 ; 结尾,不排除有其他的代码格式,比如python就没有这样的规定,那么在我们c#编程里,每有一个; 就代表程序执行一次的数据操作.例如: 

void Start() {
    Debug.Log("Hello,Unity!\n");      //  需要执行 1 次
}

上面的代码块只需要执行一次. 这个如果用大O记法,记作O(1). 

for (int i = 0 ; i<=10,i++)  //执行11次,当i=11的时候跳出循环
{
   Debug .Log ("Hello,Unity!"); //每次循环执行1次
}

上面的代码块就是2*10+1次 如果用大O计法的话应该是外层循环N乘以内层循环O(N*1),所以时间复杂度应该是O(N). 

for (int i = 0 ; i<=10,i++)  //执行11次,当i=11的时候跳出循环
{
      for (int j = 0 ; j<=6,j++)  //执行7次,当i=7的时候跳出循环
        {
           Debug .Log ("Hello,Unity!"); //执行60次
          }
}

上面的循环嵌套,当外层循环一次,内循环执行一轮,所以将会是i*j+2,同上计算方法,数据结构算法的时间复杂度表示为O(i*j).如果i=j ,可以写成O(N^2).

void Method(int n) {
    // 第一部分时间复杂度为 O(n^2)
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            printf("Hello, Uniyt!");
        }
    }
    // 第二部分时间复杂度为 O(n)
    for(int j = 0; j < n; j++) {
        printf("Hello, Uniyt!");
    }
}

当遇到上面的情况,并不是将2个循环体的时间复杂度相加,而是取时间复杂度高的那个作为整个算法的时间复杂度.所以上面的时间复杂度应该记为O(N^2).

时间复杂度分析的基本策略是：从内向外分析，从最深层开始分析。如果遇到函数调用，要深入函数进行分析,舍弃算法中时间复杂度比较低的那个模块.

最后，我们来练习一下,答案可以直接写在评论区

第一题: 

void Method(int n) {
    for (int i = 0; i < n; i++) {
        for (int j = i; j < n; j++) {
            printf("Hello Unity");
        }
    }
}

第二题:

void Method(int n) {
    for (int i = 2; i < n; i++) {
        i *= 2;
        printf(i.Tostring());
    }
}

第三题: 

void Method(int n) {
    for (int i = 0; i < n; i++) {
        i *= 3;
        printf(i.Tostring());
    }
}

附加题

void Start()
{
        method(n);
}
void method(int n) {
    if (n <= 1) {
        return 1;
    } else {
        return aFunc(n - 1) + aFunc(n - 2);
    }
}

…END…

正文完
2023-01-17