玩转算法面试--01（时间复杂度分析)

2022/2/14 1:14:57

编程Tag： 算法时间递归 int 复杂度 01 -- Logn

本文主要是介绍玩转算法面试--01（时间复杂度分析)，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

1.前言

2.究竟什么是大O？

3.数据规模的概念

4.常见的复杂度的分析：

5.时间复杂度的测试

6.递归算法的时间复杂度：（最主要的是要计算递归的深度）

7.均摊复杂度的分析：

1.前言

2.究竟什么是大O？

如果对于一个算法来说n是他的数据规模，O（f(n)）则表示运行算法所需要执行的指令数，和f(n)成正比。

时间复杂度O 衡量的是一个量级上的差距，这种量级上的差距表现在当n突破了一个点的时候，时间复杂度底的算法就一定比时间复杂度高的算法要快。而且n越大这个优势就越明显

所以当数据规模比较小的时候，前面的这个常数是有意义的。在学术界严格的来讲，O（f(n)）表示的是算法执行的上界。在业界，我们就使用O来表示算法执行的最低上界。

例题：

这个题有两个维度的变量一个是数组内字符串的长度，一个是数组有多少个元素，这两个变量毫无关联。

3.数据规模的概念

空间复杂度：

4.常见的复杂度的分析：

O（n）级别的算法有一个很明显的特征就是有一个循环，并且循环的次数是和n相关的。

所执行的指令数和n^2是成正比关系的

二分查找的时间复杂度就是O（logn）

分析：

例子：

由于增量的特殊性，第一重循环将循环logn次，sz+=sz 其实就是sz=sz*2,就是n经过几次除以2等于1 所以时间复杂度为O（n*logn）

5.时间复杂度的测试

有没有什么算法帮助我们来判断我们写的程序到底是一个什么级别的算法？数据规模每次都翻倍，观察消耗时间。

时间复杂度为O（n）的算法

    // O(n)
    public static void test1(int n) {
        int i;
        int sum;
        for (i = 0; i < n; i++) {
            /*时间复杂度为O(1)的程序*/
            sum = (1 + i) * i / 2;
        }
    }

测试代码：

        int n = 12;
        for (int i = 1; i < n; i++) {
            int pow = (int) Math.pow(2, i);
            long before = System.nanoTime();
            test1(pow);
            long after = System.nanoTime();
            long time = after - before;
            System.out.println("数据规模为2的" + i + "次方,消耗的时间为" + time);
        }

结果：

从2的6次方开始，数据规模增大一倍，所消耗的时间增大一倍