欢迎您的访问
专注架构,Java,数据结构算法,Python技术分享

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

概念

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

时间复杂度为一个算法流程中,常数操作数量的指标。常用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

赞(0) 打赏
版权归原创作者所有,任何形式转载请联系作者;码农code之路 博客站点 » 如何理解算法中的时间复杂度?

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏