如何理解算法中的时间复杂度？

阅读 1

2021-07-04

概念

常数时间的操作：一个操作如果和数据量没有关系，每次都是固定时间内完成的操作，叫做常数操作。

时间复杂度为一个算法流程中，常数操作数量的指标。常用O（读作big O）来表示。具体来说，在常数操作数量的表达式中，只要高阶项，不要低阶项，也不要高阶项的系数，剩下的部分，如果记为f(N)，那么时间复杂度为O(f(N))。

算法的时间复杂度，用来度量算法的运行时间，记作: O(f(N))。它表示随着输入大小N的增大，算法执行需要的时间的增长速度可以用 f(N) 来描述。

上面概念可能比较抽象，下面我们用案例的方式来举例下,一般我们是先拿到f(N)，然后来算下他的时间复杂度，一般我们只保留对函数增长速度较大的函数

例如:

f(N)=c（c是常数），我们称时间复杂度为
O(1)

f(N)=a*N b(a和b是常数)，我们称时间复杂度为
O(N)

f(N)=a*N^2 b*N c(a,b,c均为常数)，我们称时间复杂度为
O(N^2)

f(N)=a*N^2*logN b*N c(a,b,c均为常数)，我们称时间复杂度为
O(N^2*logN)

案例

    public String test() {
        System.out.println("hello world"); // 需要执行 1 次
        return "你好"; // 需要执行 1 次
    }

上面的代码执行了2次，则f(N)=2;则时间复杂度为O(1);

    public int test() {
        for (int i = 0; i < N; i  ) { 
            System.out.println("hello world1"); // 需要执行 N 次
            System.out.println("hello world2"); // 需要执行 N 次
        }
        System.out.println("hello world3"); // 需要执行 1 次
    }

上面的代码执行了2N 1次，则f(N)=2N 1,时间复杂度为O(N)

public int test() {
        for (int i = 0; i < N; i  ) { 
            for (int j = 0; j < N; j  ) {
                System.out.println("hello world"); // 需要执行 N*N 次
            }
        }
    }

上面的代码执行了N*N次，则f(N)=N^2，时间复杂度为O(N^2)

当出现条件或者顺序执行的语句时，总是取最大的时间复杂度,或者说最差的情况

public int test() {
        //循环1：时间复杂度为O(N^2)
        for (int i = 0; i < N; i  ) { 
            for (int j = 0; j < N; j  ) {
                System.out.println("hello world"); // 需要执行 N*N 次
            }
        }
        //循环2：时间复杂度为O(N)
        for (int i = 0; i < N; i  ) { 
            System.out.println("hello world1"); // 需要执行 N 次
        }
    }

上面代码的时间复杂度为O(N^2 N)=O(N^2)

public int test() {
        if(){
            //循环1：时间复杂度为O(N^2)
            for (int i = 0; i < N; i  ) { 
                for (int j = 0; j < N; j  ) {
                    System.out.println("hello world"); // 需要执行 N*N 次
                }
            }
        }else{
            //循环2：时间复杂度为O(N)
            for (int i = 0; i < N; i  ) { 
                System.out.println("hello world1"); // 需要执行 N 次
            }
        }
    }

上面代码的时间复杂度为O(N^2)

感谢阅读，希望对你有所帮助 :)
来源：blog.csdn.net/u010452388/article/details/80875958

 
  END
 


 题外推荐
 
 

 十期推荐

 
  【291期】你了解Log4j2中RollingFile的文件滚动更新机制吗？
  

 
 
  【292期】Linux面试最高频的5个基本问题
  

 
 
  【293期】面试官：你知道写时复制(Copy-On-Write)在Java中是如何被应用的吗？
  

 
 
  【294期】面试官：谈谈你对缓存的使用和理解
  

 
 
  【295期】面试官：已经用k8s来部署运维各个微服务的组件，是否可以不用整套微服务?
  

 
 
  【296期】面试官：详细说说对ＭＱ消息队列的理解以及主流ＭＱ的优缺点
  

 
 
  【297期】面试官：为什么在new 对象里面使用自动注入对象会报空指针异常？
  

 
 
  【298期】面试官：如何保证token的安全
  

 
 
  【299期】面试官：详细说一说MySQL InnoDB 中意向锁的作用
  

 
 
  【300期】面试官：Elasticsearch 是如何做到快速检索的
  

 
 
  

 
？ ~

以上数据来源于网络，如有侵权，请联系删除。

上一篇：面试官：幂等性的接口该如何设计?

下一篇：堆排序算法（图解详细流程）

类别