[数据结构与算法]伪代码实现几种常见的时间复杂度算法

数据结构的逻辑结构与物理结构

• 描述数据的几个单位

1. 数据项 （描述一个事物的基本信息，例如name是一个数据项，age是一个数据项，类似Java中的属性）
2. 数据元素 (一组数据项的集合，类似Java中的对象)
3. 数据对象 （一组相同的数据元素的集合，类似Java中的数组或集合）

• 数据结构的逻辑结构

逻辑结构就是我们可以用现实世界的语言来描述多个数据元素之间的结构，主要为四种结构：

1. 集合
2. 线性结构（ 一对一）典型实现如线性表、串、栈、队列
3. 树形结构（一对多）典型实现如二叉树、B树
4. 图形结构（网状结构）（多对多）典型实现如邻接矩阵，邻接表

• 数据结构的物理结构（存储结构）

逻辑结构表示的是元素与元素之间可以存在哪些结构关系，但是在真正用计算机存储的时候该如何存？
物理结构或存储结构可分为顺序存储和非顺序存储。可以有 顺序存储、链式存储、索引存储、散列存储这个四种存储方式，后三种可统归为非顺序存储。顺序存储和非顺序存储区分与内存地址是否是连续的。上述所说的线性表、串、堆，二叉树等都可以分别用顺序存储或非顺序存储实现。

算法的时间复杂度

• 在计算时间复杂度时，一般会去掉常数项并且只保留最高阶项同时如果最高阶项的系数不为1，则去掉系数。如以下的时间复杂度计算

2n +5 = O(n)
n^2 + 2n +5 = O(n^2)
2n^2 + 2n +5 = O(n^2)
2n^3 +5 = O(n^3)
5 = O(1)

• 各种时间复杂度的排序

O(1) < O(log2n (log以2为底n的对数) ) < O(n) < O(nlog2n) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)

• 使用伪代码实现常见的几种时间复杂度

1. O(1)

    @Test
    public void test1() {
        test1(5);
    }

    //时间复杂度O1，无论输入规模有多大，时间复杂度都是常数
    public void test1(int n){
        int i = n * 2;
    }

2. O(log2n)

    @Test
    public void test2() {
        test2(100);
    }

    //输入规模是100，这里的变量i是每次×2，相当于2 4 8 16 32 64 128 2^x = 100 ==> x = log2^100
    private void test2(int n) {
        for (int i = 1;i <= n; i = i * 2){
            System.out.println(i);
        }
    }

如果i是每次i*3的话，那么执行次数就是 log3^100

3.O(n)

    @Test
    public void test3() {
        test3(100);
    }

    //可以看出来，for循环的次数完全取决于输入规模n的大小，此时的时间复杂度就是O(n)
    private void test3(int n) {
        for (int i = 1; i < n; i++) {
            System.out.println(i);
        }
    }

4. O(nlog2n)

    @Test
    public void test4() {
        test4(100);
    }

    //nlog2^n 假设n为100，此时执行次数为100 * 7 = 700次
    private void test4(int n) {
        int count = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j < n; j = j * 2) {
                System.out.println(count++);
            }
        }

    }

5. O(n^2)

    @Test
    public void test5() {
        test5(100);
    }

    //n^2 = 100 * 100 = 10000
    private void test5(int n) {
        int count = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                System.out.println(count++);
            }
        }
    }

6. O(n^3)

o^3效率非常可怕，执行了几十秒才完成

    @Test
    public void test6() {
        test6(100);
    }

    //n^3 = 100 * 100 * 100 = 1000000
    private void test6(int n) {
        int count = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                for (int k = 1; k <= n ; k++) {
                    System.out.println(count++);
                }
            }
        }
    }

7.O(2^n)
算力爆炸的计算机可以执行以下，我的电脑已经奔溃了。

    @Test
    public void test7() {
        test7(100);
    }

    //这个算法的复杂度是2^n + n = 2^n
    private void test7(int n) {
        int sum = 1;
        for (int i = 1; i <= n ; i++) {
            sum = sum * 2;
        }
        for (int i = 0; i < sum ; i++) {
            System.out.println(i);
        }
    }

8. n！

    @Test
    public void test8() {
        test8(8);
    }

    //先计算出n的阶乘，又执行了n的阶乘的for循环 时间复杂度 n! + n = n!
    private void test8(int n) {
        int je = 1;
        for (int i = n; i > 0; i--) {
            je = je * i;
        }
        for (int i = 0; i < je; i++) {
            System.out.println(i);
        }
    }