初识数据结构

目录

一.数据结构

1. 什么是数据结构

2. 如何学好数据结构

二.集合框架

三.算法效率 (时间复杂度和空间复杂度)

1. 时间复杂度

2. 空间复杂度

---

一.数据结构

1. 什么是数据结构

数据结构(Data Structure)是计算机储存,组织数据的方式, 指相互之间存在一种或多种特定关系的数据元素的集合. 数据结构是一门单独的学科,和语言没有关系 (用C / C++ / Java 等语言均可实现). 数据结构 = 数据 + 结构. 数据结构和数据库的关系是: 数据库的背后,需要数据结构来支持.

2. 如何学好数据结构

数据结构十分抽象,有时必须结合图形来思考.所以想要学好数据结构,我们需要: 多画图,多思考,多写练习(写代码 / 刷题).

二.集合框架

Java集合框架(Java Collection Framework) , 又被称为容器(Container) ,  是定义在java.util包下的一组接口及其实现类. 其主要作用表现为将多个元素置于一个单元中,对这些元素进行快速,便捷的"增删查改". 

三.算法效率 (时间复杂度和空间复杂度)

1. 时间复杂度

时间复杂度(又称时间效率), 主要衡量的是一个算法的运行速度.一般用算法中基本操作的执行次数来表示.

实际中我们计算时间复杂度时, 并不需要计算精确的执行次数, 而只需要一个大概的数字.所以这里我们可以使用大O的渐进表示法.(大O渐进法去掉了那些对结果影响不大的项, 简洁地表示出了一个算法大概的执行次数).

推导大O阶的方法:

(1) 用常数1取代所有加法常数.

(2) 在经过(1)步骤修改后的表达式中, 只保留最高阶项.

(3) 若最高阶项不是1, 则去掉最高阶项的常系数, 得到的结果就是大O阶. (若最高阶项为1, 则时间复杂度就是1).

代码示例:

public class test {
    void func(int N){
        int count = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                count++; //N*N 次
            }
        }
        for (int k = 0; k < 2*N; k++) {
            count++; //2N次
        }
        int M = 10;
        while ((M--) > 0) {
            count ++; //10次
        }
    }
}

上述代码基本操作执行次数为: + 2N + 10;

 按推导大O阶的方法来计算:

(1)  + 2N + 1

(2)

(3)

所以此代码的时间复杂度为: O()

2. 空间复杂度

空间复杂度, 主要衡量的是一个算法所需要占用的空间. 一般用算法中变量的个数来表示.

我们在计算空间复杂度时, 同样可以用大O渐进法来大概表示.

代码示例:

public class test {
    void bubbleSort(int[] array){
        for (int end = array.length; end > 0; end--) {
            boolean sorted = true;
            for (int i = 1; i < end; i++) {
                if(array[i-1] > array[i]) {
                    //...
                }
            }
        }
    }
}

冒泡排序, 仅创建了一个数组, 在内存上开辟了一块空间. 所以此算法的空间复杂度为O(1).

public class test {
    long fac(int N) {
        return N < 2 ? N : fac(N - 1)*N;
    }
}

递归求阶乘, 递归调用了N次,开辟了N个栈帧. 所以此算法的空间复杂度为O(N) .

 那么,以上就是本篇博客的全部内容啦,如果喜欢小编的文章,可以点赞,评论,收藏~