算法基础学习1——时间复杂度和空间复杂度

简介: 算法基础学习1——时间复杂度和空间复杂度

🟡前言


本文是21天学习挑战赛的第一天,会有一个系列的文章重新梳理算法,本文主要是描述时间复杂度和空间复杂度

活动地址:CSDN21天学习挑战赛


🟡时间复杂度


1️⃣实例说明


public class test {
    public static void main(String[] args) {
        int i = 1 , sum = 0;
        for(i = 0 ; i <= 100 ; i += 1){
            sum = sum +i;
        }
        System.out.println("和是:"+sum);
    }
}
public class 运用for语句求和 {
    public static void main(String[] args) {
        int sum = 0;
        int n = 100;
        sum = (n+1)*n/2;
        System.out.println("和是:" + sum);
    }
}


上面两个程序的执行时间不同;第一个程序需要执行100次累加语句,而第二个程序只需要执行三次运算,这就牵涉到时间复杂度


2️⃣时间复杂度分析


ea8a94f1c3e8497ab04ed2ae7e93cdcc.png


如上图所示,可得出结论:算法函数中n最高次幂越小,算法效率越高


在比较算法随着输入规模的增长量时,规则如下


  • 算法函数中的常数可以忽略
  • 算法函数中最高次幂的常数因子可以忽略
  • 算法函数中最高次幂越小,算法效率越高


3️⃣算法时间复杂度计法


(1)大O记法


大O记法的规则如下:


  • 用1取代运行时间中所有的加法常数
  • 修改后的运行次数中,只保留高阶项
  • 若高阶项存在且系数不为1,则去除系数


下面是一些实例


public static void main(String[] args){
  int sum =0;//执行1次
  int n = 100;//执行1次
  sum = (n+1)*n/2//执行1次
}


这个程序执行了 3 次,根据规则记为O(1)


public class test {
    public static void main(String[] args) {
        int sum = 0;
        int n = 100;//执行1次
        for(i = 0 ; i <= n ; i += 1){
            sum = sum +i;//执行n次
        }
        System.out.println("和是:"+sum);
    }
}


这个程序执行了 n+1 次,记为 O(n)


public class test {
    public static void main(String[] args) {
        int sum = 0;//执行1次
        int n = 100;//执行1次
        for(i = 0 ; i <= n ; i += 1){
          for(j = 1 ; j <=n ; j++){
              sum = sum +i;//执行n^2次
            }
        }
        System.out.println("和是:"+sum);
    }
}


这个程序执行了 n^2+1 次,记为 O(n^2)


(2)常见大O阶


  • 线性阶


非嵌套语句涉及;随输入规模扩大,计数次呈直线增长


public static void main(String[] args) {
  int i = 1 , sum = 0;
    for(i = 0 ; i <= 100 ; i += 1){
      sum = sum +i;
    }
    System.out.println("和是:"+sum);
}


  • 平方阶


一般嵌套语句涉及


public static void main(String[] args) {
  int sum = 0;//执行1次
    int n = 100;//执行1次
    for(i = 0 ; i <= n ; i += 1){
      for(j = 1 ; j <=n ; j++){
          sum = sum +i;//执行n^2次
        }
    }
  System.out.println("和是:"+sum);
}


  • 立方阶


一般三层嵌套循环涉及


public static void main(String[] args) {
  int sum = 0;//执行1次
    int x = 100;//执行1次
    for(int i = 1 ; i <= n ; i++){
      for(int j = i ; j <=n ; j++){
        for(int j =i; j <=n; j++){
            x++
          }
        }
    }
  System.out.println("和是:"+sum);
}


  • 对数阶


int i = 1, n = 100;
while(i<n){
  i = i*2
}


  • 常数阶


public static void main(String[] args) {
int n = 100;
int i = n+2;
System.out.println(i);
}


时间复杂度总结如下


b549162a44274c109b9f0803401312ca.jpg


(3)方法调用时间复杂度


只要将方法体内语句代替方法名,即可用上述方法求出时间复杂度


public class Test4 {
    public static void main(String[] args) {
        int n = 100;
        show(n);//执行n次
        for(int i = 0; i < n; i++){
            show(i);//执行n次
        }
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                System.out.println(j);//执行n^2次
            }
        }
    }
    private static void show(int i) {
        for (int j = 0; j < i; j ++){
            System.out.println(i);//执行n次
        }
    }
}


总共执行:n + n * n + n^2 = 2n ^2 + n 次


所以时间复杂度为:O(n^2)


(4)最坏情况


最坏情况指将程序运行到最后一种情况才是期望的目标,在考虑时间复杂度时要考虑最坏情况


🟡空间复杂度


1️⃣Java中常见内存占用


数据类型 占用字节数
byte 1
short 2
int 4
long 8
float 4
double 8
boolean 1
char 2


2️⃣创建对象内存占用


  • 计算机一次访问一个字节
  • 每个对象自身开销16字节,用来保存对象头信息
  • 一个引用(机器地址)需要8字节
  • 内存若不够8字节(或其倍数),自动填充为8字节(或其倍数)
  • 一个原始数据类型的数组需要24字节的头信息
    (16字节自己对象开销+4字节保存长度+4字节填充为8整数倍)


🟡结语


从下一篇文章起会分享有关算法中排序的知识点以及对应习题

相关文章
|
15天前
|
存储 算法
数据结构与算法学习二二:图的学习、图的概念、图的深度和广度优先遍历
这篇文章详细介绍了图的概念、表示方式以及深度优先遍历和广度优先遍历的算法实现。
30 1
数据结构与算法学习二二:图的学习、图的概念、图的深度和广度优先遍历
|
9天前
|
搜索推荐 算法
插入排序算法的平均时间复杂度解析
【10月更文挑战第12天】 插入排序是一种简单直观的排序算法,通过不断将未排序元素插入到已排序部分的合适位置来完成排序。其平均时间复杂度为$O(n^2)$,适用于小规模或部分有序的数据。尽管效率不高,但在特定场景下仍具优势。
|
12天前
|
缓存 算法 Java
JVM知识体系学习六:JVM垃圾是什么、GC常用垃圾清除算法、堆内存逻辑分区、栈上分配、对象何时进入老年代、有关老年代新生代的两个问题、常见的垃圾回收器、CMS
这篇文章详细介绍了Java虚拟机(JVM)中的垃圾回收机制,包括垃圾的定义、垃圾回收算法、堆内存的逻辑分区、对象的内存分配和回收过程,以及不同垃圾回收器的工作原理和参数设置。
36 4
JVM知识体系学习六:JVM垃圾是什么、GC常用垃圾清除算法、堆内存逻辑分区、栈上分配、对象何时进入老年代、有关老年代新生代的两个问题、常见的垃圾回收器、CMS
|
13天前
|
算法
动态规划算法学习三:0-1背包问题
这篇文章是关于0-1背包问题的动态规划算法详解,包括问题描述、解决步骤、最优子结构性质、状态表示和递推方程、算法设计与分析、计算最优值、算法实现以及对算法缺点的思考。
40 2
动态规划算法学习三:0-1背包问题
|
13天前
|
算法
动态规划算法学习四:最大上升子序列问题(LIS:Longest Increasing Subsequence)
这篇文章介绍了动态规划算法中解决最大上升子序列问题(LIS)的方法,包括问题的描述、动态规划的步骤、状态表示、递推方程、计算最优值以及优化方法,如非动态规划的二分法。
48 0
动态规划算法学习四:最大上升子序列问题(LIS:Longest Increasing Subsequence)
|
13天前
|
算法
动态规划算法学习二:最长公共子序列
这篇文章介绍了如何使用动态规划算法解决最长公共子序列(LCS)问题,包括问题描述、最优子结构性质、状态表示、状态递归方程、计算最优值的方法,以及具体的代码实现。
55 0
动态规划算法学习二:最长公共子序列
|
13天前
|
缓存 负载均衡 算法
nginx学习:配置文件详解,负载均衡三种算法学习,上接nginx实操篇
Nginx 是一款高性能的 HTTP 和反向代理服务器,也是一个通用的 TCP/UDP 代理服务器,以及一个邮件代理服务器和通用的 HTTP 缓存服务器。
19 0
nginx学习:配置文件详解,负载均衡三种算法学习,上接nginx实操篇
|
13天前
|
存储 算法
动态规划算法学习一:DP的重要知识点、矩阵连乘算法
这篇文章是关于动态规划算法中矩阵连乘问题的详解,包括问题描述、最优子结构、重叠子问题、递归方法、备忘录方法和动态规划算法设计的步骤。
56 0
|
3天前
|
算法 安全 数据安全/隐私保护
基于game-based算法的动态频谱访问matlab仿真
本算法展示了在认知无线电网络中,通过游戏理论优化动态频谱访问,提高频谱利用率和物理层安全性。程序运行效果包括负载因子、传输功率、信噪比对用户效用和保密率的影响分析。软件版本:Matlab 2022a。完整代码包含详细中文注释和操作视频。
|
21天前
|
机器学习/深度学习 算法 数据安全/隐私保护
基于MSER和HOG特征提取的SVM交通标志检测和识别算法matlab仿真
### 算法简介 1. **算法运行效果图预览**:展示算法效果,完整程序运行后无水印。 2. **算法运行软件版本**:Matlab 2017b。 3. **部分核心程序**:完整版代码包含中文注释及操作步骤视频。 4. **算法理论概述**: - **MSER**:用于检测显著区域,提取图像中稳定区域,适用于光照变化下的交通标志检测。 - **HOG特征提取**:通过计算图像小区域的梯度直方图捕捉局部纹理信息,用于物体检测。 - **SVM**:寻找最大化间隔的超平面以分类样本。 整个算法流程图见下图。