数据结构和算法

数据结构与算法—基础篇

2020-04-06  本文已影响0人  小满豆

一、数据结构

概念

数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率。数据结构往往同高效的检索算法和索引技术有关。数据结构分为逻辑结构和物理结构。

数据结构组成
逻辑结构

指反映数据元素之间的逻辑关系的数据结构，其中的逻辑关系是指数据元素之间的前后间关系，而与他们在计算机中的存储位置无关。数据的逻辑关系包括：

物理结构

数据的逻辑结构在计算机存储空间中的存放形式称为数据的物理结构(也称为存储结构)。

数据的物理结构的特点是：

常见数据结构
常见数据结构

二、算法

概念

算法是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。

数据结构和算法的关系
算法知识点

输入输出：算法可以有0个或者多个输入；算法至少要有一个输出，没有输出的算法也就没有意义。
有穷性：算法必须要在执行有限个步骤之后产生出结果。
确定性：算法的每个步骤都要有确切的意义。
可行性：算法的每个步骤都要切实有效，可执行。

正确性：算法被要求结果一定正确，不正确就没有意义了。
健壮性：算法内的逻辑处理要考虑到对不合理数据的处理，即容错能力。
可读性：即算法可供其他人阅读的能力。
时间复杂度：执行算法所需要的计算工作量或时间长短。一般用O(n)表示，n越大时间复杂度越大。一般作为衡量算法效率的主要方法。
空间复杂度：执行算法所需要的辅助（额外使用的）内存空间大小。也可用O(n)表示，计算比时间复杂度简单。

算法的时间复杂度
时间复杂度计算规则
时间复杂度常见计算情况
//时间复杂度  1+1+1+1+1+1 = 6  O(1)
void testSum1(int n) {
    int sum = 0;   //执行1次
    sum = (1 + n) * 2; //执行1次
    sum = (1 + n) * 2; //执行1次
    sum = (1 + n) * 2; //执行1次
    sum = (1 + n) * 2; //执行1次
    sum = (1 + n) * 2; //执行1次
}

//时间复杂度  1 + n = n   O(n)
void testSum2(int n) {
    int x = 0;
    for (int i = 0; i < n; i ++) {
        x = x + 1; //执行n次
    }
}
//时间复杂度  1 + (n + 1) + n = 2n + 2  O(n)
void testSum3(int n) {
    int x = 0;  // 1次
    for (int i = 0; i <= n; i ++) {
        x = x + 1; //执行 n + 1 次
    }
    for (int j = 0; j < n; j ++) {
        x = x * 2; //执行 n 次
    }
}

//时间复杂度  1 + n + n^2   O(n^2)
void testSum4(int n) {
    int x = 0; // 1次
    for (int i = 0; i < n; i ++)
    {
        x = x + 1;  //执行 n 次
        for (int j = 0; j < n; j ++)
        {
            x = x + 1; //执行 n^2 次
        }
    }
}
//时间复杂度  n*(n+1)/2 = n^2/2 + n/2  O(n^2)
void testSum5(int n) {
    int x = 0;
    for (int i = 0; i < n; i ++) {
        for (int j = i; j < n; j ++) {
            x = x + 1;
            /** 等差数列求和
             i = 0, 执行n次
             i = 1， 执行n-1次
             i = 2， 执行n-2次
             ...
             i = n-1, 执行 1 次
             
             执行总次数：n*(n+1)/2
             */
        }
    }
}

//时间复杂度 假如x是执行次数  2 ^ x >= n , x = log(2)(n)  O(logn)
void testSum6(int n) {
    int count = 1;
    while (count < n) {
        count = count * 2;  //执行 log(2)(n)次
    }
}

//时间复杂度 n + n*n + n*n*n     O(n^3)
void testSum7(int n) {
    int x = 1;
    for (int i = 0; i < n; i ++) {
        x = x + 1; //n次
        for (int j = 0; j < n; j ++) {
            x = x + 1;//n*n次
            for (int k = 0; k < n; k ++) {
                x = x + 1;//n*n*n次
            }
        }
    }
}
时间复杂度常见情况

时间复杂度的大小如下：
O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)

算法的空间复杂度

一个算法执行的过程中可能用到的空间因素有：

例子：数组逆序,将一维数组a中的n个数逆序存放在原数组中（n<=a.count）。
方法一：只使用了一个中间变量temp，空间复杂度 O(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;
    }

方法二：数组b中创建了n个元素，空间复杂度是O(n)

    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];
    }

总结

上一篇 下一篇

猜你喜欢

热点阅读