[数据结构与算法] 【久远讲算法】什么是时间复杂度

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 【久远讲算法】什么是时间复杂度 -> 正文阅读

[数据结构与算法]【久远讲算法】什么是时间复杂度

title: 【久远讲算法】什么是时间复杂度
date: 2021-10-07 22:09:47
tags:

java
data structure
categories:
java
data structure

大家好，我是久远，今天开始，由我来给大家分享算法以及数据结构的相关知识。

什么是算法

今天我们先来讨论一个问题：什么是算法？

算法是指计算方法么？并不准确。

算法这个名称虽然听着硬核，但是我们换个场景你就会非常熟悉。

小学数学课上，你是不是可以用 3+3+3 或者 3*3 来解决三个三相加这个问题，虽然算的结果都是9，但是中间我们用的方法是不一样的。

假如你今天要做一道菜，你是不是需要菜谱，菜谱上肯定会告诉你，你做这个菜需要什么材料，分几步完成，完成这道菜需要多久。

而我们今天要讲的算法，就是计算机编程界的菜谱，它就是计算机解决问题的方法。用不同的办法去解决同一个问题，结果虽然都一样，但是过程可能千差万别。

正因为计算机解决问题的方法有很多个，我们便要拿标准去衡量，到底哪些算法更好，更适合我们去使用。

时空复杂度

怎么衡量一个算法的好坏呢？

举个现实的例子：

小明和小亮去企业面试，hr要求他们用代码实现一个需求，一天之后，两个人交付了各自的代码，都能实现hr的需求。而只有小明被录用了。这是因为：

小明的代码运行一次花了50ms,内存占用5MB。

而小亮的代码运行一次要花10s，占用内存50MB。

小亮的代码虽然能够实现功能，但是运行时间和内存占用都没有小明的少，自然没有被录用。

所以我们衡量代码的好坏要从时间和空间两个角度去考虑。即：

时间复杂度
空间复杂度

在本文中，我们先讲解空间复杂度。

时间复杂度

我们可以将时间复杂度划分为两个小概念：

基本操作次数
渐进时间复杂度

基本操作次数

我们假设计算机运行一行基础代码执行一次运算。

void T0101(){
System.out.print("hello world!"); //执行一次
}

这个方法需要执行1次运算。

void T0102(int n){
for(int i = 0; i < n; i++){// 再计算for循环外层执行次数 n+1 次
System.out.print("hello world!")//先计算for循环里层执行的次数 n次
}
}

上面这个方法需要执行（n+1+n）= 2n+1 次运算。

我们把算法需要执行的运算次数用输入大小n 的函数表示，即 T(n).

为了估算算法需要的运行时间和简化算法分析，我们引入时间复杂度的概念。

我们再来看几个例子：

$T (n) = 3 n$ ,执行次数是线性的。

void T0103(int n){
for(int i = 0; i < n; i++){ // 外层循环n次 
System.out.print("一"); //执行一次
System.out.print("二"); //执行一次
System.out.print("三"); //执行一次
}
}

$T (n) = 5 l o g n$ ,执行次数是用对数计算的。

void T0104(int n){
    for(int i = n; i>1; i/=2){//观察n与i的运算关系 成对数关系
        System.out.println("一");//执行一次
        System.out.println("二");//执行一次
        System.out.println("三");//执行一次
        System.out.println("四");//执行一次
        System.out.println("五");//执行一次
    }
}

$T (n) = 2$ , 执行次数是常量。

void T0105(int n){
    System.out.println("一");//没有循环次数
    System.out.println("二");//只需要输出两次内容执行次数为2
}

$ T(n) = n^2$ ,执行次数为幂函数。

void T0106(int n) {
    for(int i = 0; i < n; i++) { // 循环次数为 n
        for(int j = 0; j < n; j++) {// 循环次数为 n
            System.out.println("Hello, World!"); // 							循环体时间复杂度为 O(1)
        }
    }
}