标签：计算机   基本   反转   com   填充   table   指令   估算   class   

数据结构和算法概述

算法分析

• 目的：花费更少的时间和更少的内存

1.1时间复杂度分析

• 事后分析方法：

  程序开始时获取一个时间，结束时又获取一个时间，两者相减即可获得运行时间。

  例：

  public class demo {
      public static void main(String[] args) {
          long start = System.currentTimeMills();
          
          long result = fun(10);
          System.out.println(result);
          
          long end = System.currentTimeMills();
          System.out.println(end-start);
      }
  ?
      public static long fun(long n){
          int result = 1;
          for(long i = 1;i n;i++){
              result *= i;
          }
          return result;
      }
  }

弊端：必须将程序写好，跑一遍，意味着如果跑出来的结果不理想，自己花费几天时间写的这个算法时间和精力都白费了；容易受硬件影响结果。

1.2空间复杂度分析

• java中常见内存占用情况

  • 基本数据类型

    数据类型	内存占用情况
    byte	1
    short	2
    int	4
    long	8
    float	4
    double	8
    boolean	1
    char	2

  • 计算机访问内存都是一次一个字节（8位）

  • 一个引用（变量/机器地址）需要8个字节表示

  • 创建一个对象，除了对象内部数据要花费内存，其对象本身也要花费16字节内存来保存对象的头信息

  • 一般内存的使用不够8字节的倍数，都会被自动填充够8字节的倍数

  • 一个原始数据类型数组使用了24个字节（其中16字节用来保存数组对象的头信息，4字节用来保存长度，4字节自动填充）

• 案例：对数组元素进行反转，并返回

  解法一：

  public static int[] reverse1(int[] arr) {
      int n = arr.lenght;   //申请4个字节
      int[] temp = new int[n];    //申请n*4个字节+数组头信息开销24个字节
      for(int i=0;in;i++){
          temp[n-1-i] = arr[i];
      }
      return temp;
  }

  忽略判断条件占用的内存，内存开销为4n+24+4即空间复杂度为O（n）。

  解法二：

  public static int[] reverse2(int[] arr) {
      int n = arr.lenght;     //申请4个字节
      int[] temp;             //申请4个字节
      for(int start=0,end=n-1;startend;start++,end--){
          temp = arr[start];
          arr[start] = arr[end];
          arr[end] = temp;
      }
      return arr;
  }

  忽略判断条件占用的内存，内存开销为4+4即空间复杂度为O（1）。

数据结构和算法概述02

标签：计算机   基本   反转   com   填充   table   指令   估算   class   

原文地址：https://www.cnblogs.com/flc-sept18/p/14544252.html