前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >数据结构与算法(一)

数据结构与算法(一)

作者头像
拉维
发布2022-03-28 09:16:14
3020
发布2022-03-28 09:16:14
举报
文章被收录于专栏:iOS小生活

一、逻辑结构和物理结构的区别

1,数据结构——逻辑结构

逻辑结构表述的是数据与数据之间的逻辑关系

(1)集合结构

所有的数据都属于同一个集合,数据元素之间没有先后顺序

(2)线性结构

数据与数据之间是一对一的关系。凡是符合一对一关系的结构都是线性结构,比如线性表、队列、栈、数组、字符串等。

(3)树形结构

特点:数据元素之间的关系是一对多。凡是符合一对多关系的结构都是树形结构,比如:二叉树、红黑树等。

(4)图形结构

特点:数据关系多对多。凡是存在多对多关系的结构都是图形结构。

2,数据结构——物理结构

上线提到了,逻辑结构描述的是数据与数据之间的逻辑关系,这些数据之间的关系无论多么复杂,最终都还是要存储到内存中的,数据在内存中的结构体现就是物理结构。

(1)顺序存储结构

开辟一段连续的内存,将数据依次存储进去。

(2)链式存储结构

特点:不需要提前开辟一段连续的空间。

二、时间复杂度

我们在设计算法的时候(写业务代码也同样适用),要按如下的要求去检查和优化自己的代码:正确性->健壮性->可读性->时间效率高和存储量低

首先,要优先保证你的代码能够准确的将业务展现出来,想想看,如果你的代码都不能正确地表达业务,那么代码的可读性再好、性能再高又有什么用呢?

其次,要保证代码具有足够强的容错性,不要动不动就Crash,要能够兼容大部分的异常场景;

然后,在保证正确性和健壮性的基础上,要让你的代码能够容易被别人读懂

最后,在保证前三者的基础之上,再考虑去做性能上的优化,比如算法层面的时间空间复杂度、UI层面的卡顿优化内存优化等。

那么如何去评判一个算法的时间效率高呢?用的就是时间复杂度

在这里,我们使用大O表示法来表示时间复杂度,大O表示法有如下规则:

  1. 用常数1来取代运行时间中的所有常数
  2. 在修改运行次数函数中,只保留最高阶项
  3. 如果最高阶存在且不等于1,则去除该项目相乘的常数

常见的时间复杂度术语,由小到大排列:

  1. 常数阶
  2. 对数阶
  3. 线性阶
  4. nlogn阶
  5. 平方阶
  6. 立方阶
  7. 指数阶

1,常数阶

O(1)

示例如下:

代码语言:javascript
复制
// 1+1+1=3,所有的常数都用1来替代,所以是O(1)
void testSum1(int n){
    int sum = 0;                              //执行1次
    sum = (1+n)*n/2;                      //执行1次
    printf("testSum1:%d\n",sum); //执行1次
}

// 1+1+1+1+1+1+1=7,所有的常数都用1来替代,所以是O(1)
void testSum2(int n){
    int sum = 0;                    //执行1次
    sum = (1+n)*n/2;            //执行1次
    sum = (1+n)*n/2;            //执行1次
    sum = (1+n)*n/2;            //执行1次
    sum = (1+n)*n/2;            //执行1次
    sum = (1+n)*n/2;            //执行1次
    printf("testSum2:%d\n",sum); //执行1次
    
}

// O(1)
void add(int x){
    x = x+1; // 执行1次
}

2,对数阶

O(logn)

代码语言:javascript
复制
void testA(int n){
    int count = 1;
    while (count < n) {
        count = count * 2;
    }
}

看上面这个例子,如果执行1次,那么 count * 2 = n;

如果执行2次,那么 count * 2^2 = n;

如果执行3次,那么 count * 2^3 = n;

……

如果执行x次,那么 count * 2^x = n;

那么x = log2n,常数均替换为1,那么x = logn

所以时间复杂度是O(logn)

3,线性阶

O(n)

示例如下:

代码语言:javascript
复制
// x=x+1; 这行代码执行n次,O(n)
void add2(int x,int n){
    for (int i = 0; i < n; i++) {
        x = x+1;
    }
}

// 一共执行1+(n+1)+n+1 = 3+2n 次,将所有常数替换为1,因此是 O(n)
void testSum3(int n){
    int i,sum = 0;                  //执行1次
    for (i = 1; i <= n; i++) {   //执行n+1次
        sum += i;                    //执行n次
    }
    printf("testSum3:%d\n",sum);  //执行1次
}

4,nlogn阶

后面会在实例中介绍,这里不做介绍。

5,平方阶

O(n^2)

示例如下:

代码语言:javascript
复制
//x=x+1; 这行代码执行了n*n次,所以时间复杂度是O(n^2)
void add3(int x,int n){
    for (int i = 0; i< n; i++) {
        for (int j = 0; j < n ; j++) {
            x=x+1;
        }
    }
}

再看一个例子:

代码语言:javascript
复制
void testSum4(int n){
    int sum = 0;
    for(int i = 0; i < n;i++)
        for (int j = i; j < n; j++) {
            sum += j;
        }
    printf("textSum4:%d",sum);
}

当i=0时,sum += j;这句代码执行n次;

当i=1时,sum += j;这句代码执行n-1次;

当i=2时,sum += j;这句代码执行n-2次;

……

当i=n-1时,sum += j;这句代码执行1次;

所以一共执行n+(n-1)+(n-2)+…+1=(1+n)*n/2=(n^2+n)/2

所有常数项替换为1,并且只保留最高阶项,所以时间复杂度是O(n^2)

再看下面这个例子:

代码语言:javascript
复制
void testSum5(int n){
    int i,j,x=0,sum = 0;
    for (i = 1; i <= n; i++) {
        for (j = 1; j <= n; j++) {
            x++;
            sum = sum + x;
        }
    }
    printf("testSum5:%d\n",sum);
}

可以将下面这两行代码看成是一个整体代码块,那么这个整体代码块一共执行了n*n次,因此时间复杂度是O(n^2)

6,立方阶

O(n^3)

示例如下:

代码语言:javascript
复制
void testB(int n){
    int sum = 1;                         //执行1次
    for (int i = 0; i < n; i++) {        //执行n次
        for (int j = 0 ; j < n; j++) {   //执行n*n次
            for (int k = 0; k < n; k++) {//执行n*n*n次
                sum = sum * 2;          //执行n*n*n次
            }
        }
    }
}

7,指数阶

O(2^n)或者O(n!)

指数级的时间复杂度在实际项目中是很少预见的,如果一个人能写出指数级时间复杂度的代码,那么这个人也真是神人了。对于指数阶,除非是n特别小,否则将会造成噩梦般的时间消耗,所以我们一般是不会考虑指数级时间复杂度的代码的。

三、空间复杂度

空间复杂度指的是,算法在执行过程中所需的辅助空间

看下面这个例子:

代码语言:javascript
复制
    int n = 5;
    int a[10] = {1,2,3,4,5,6,7,8,9,10};
    
    //算法实现(1)
    int temp;
    for(int i = 0; i < n/2 ; i++){
        temp = a[i];
        a[i] = a[n-i-1];
        a[n-i-1] = temp;
    }

上例中是将数组a[10]给倒序,过程中只使用到了一个临时变量temp,也就是说辅助空间只有1个,因此空间复杂度是O(1)

还是给数组倒序,我接下来换一种算法实现:

代码语言:javascript
复制
    int n = 5;
    int a[10] = {1,2,3,4,5,6,7,8,9,10};
  
    //算法实现(2)
    int b[10] = {0};
    for(int i = 0; i < n;i++){
        b[i] = a[n-i-1];
    }
    for(int i = 0; i < n; i++){
        a[i] = b[i];
    }

在这种算法中,数组b就是辅助空间,一共为数组b开辟了n个元素,因此使用到了n个辅助空间,所以空间复杂度是O(n)

另外需要说明的一点是,我们在衡量一个算法的时候,是要根据该算法可能出现的最差的情况去衡量

以上。

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2022-03-09,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 iOS小生活 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档