Java数据结构通关时间复杂度和空间复杂度

目录
  • 算法效率
  • 时间复杂度
  • 空间复杂度
  • 小结

算法效率

算法效率分析分为两种:第一种是时间效率,第二种是空间效率。时间效率被称为时间复杂度,而空间效率被 称作空间复杂度。 时间复杂度主要衡量的是一个算法的运行速度,而空间复杂度主要衡量一个算法所需要的额 外空间,在计算机发展的早期,计算机的存储容量很小。所以对空间复杂度很是在乎(以前是以时间换空间).但是经过计算机行业的 迅速发展,计算机的存储容量已经达到了很高的程度。所以我们如今已经不需要再特别关注一个算法的空间复 杂度(现在是以空间换时间)。

时间复杂度

时间复杂度的定义:在计算机科学中,算法的时间复杂度是一个函数,它定量描述了该算法的运行时间。一个算法执行所耗费的时间,从理论上说,是不能算出来的,只有你把你的程序放在机器上跑起来,才能知道。但 是我们需要每个算法都上机测试吗?是可以都上机测试,但是这很麻烦所以才有了时间复杂度这个分析方 式。一个算法所花费的时间与其中语句的执行次数成正比例, 算法中的基本操作的执行次数,为算法的时间复 杂度。 实际中我们计算时间复杂度时,我们其实并不一定要计算精确的执行次数,而只需要 大概执行次数,那么这里我们使用大 O 的渐进表示法。 大 O 符号( Big O notation ):是用于描述函数渐进行为的数学符号。 推导大 O 阶方法:

1 、用常数 1 取代运行时间中的所有加法常数。

2 、在修改后的运行次数函数中,只保留最高阶项。

3 、如果最高阶项存在且不是 1 ,则去除与这个项目相乘的常数。得到的结果就是大 O 阶

来看些例子:

// 请计算一下func1基本操作执行了多少次?
void func1(int N){
   int count = 0;
   for (int i = 0; i < N ; i++) {
       for (int j = 0; j < N ; j++) {
           count++;
       }
   }
   for (int k = 0; k < 2 * N ; k++) {
       count++;
   }
   int M = 10;
  while ((M--) > 0) {
       count++;
   }
 System.out.println(count);
}

通过上面我们会发现大 O 的渐进表示法 去掉了那些对结果影响不大的项 ,简洁明了的表示出了执行次数。

另外有些算法的时间复杂度存在最好、平均和最坏情况:

最坏情况:任意输入规模的最大运行次数 ( 上界 )

平均情况:任意输入规模的期望运行次数

最好情况:任意输入规模的最小运行次数 ( 下界 )

例如:在一个长度为 N 数组中搜索一个数据 x

最好情况: 1 次找到

最坏情况: N 次找到

平均情况: N/2 次找到

在实际中一般情况关注的是算法的最坏运行情况,所以数组中搜索数据时间复杂度为 O(N)

例子二

// 计算func2的时间复杂度?
void func2(int N) {
int count = 0;
for (int k = 0; k < 2 * N ; k++) {
   count++; }
int M = 10;
while ((M--) > 0) {
   count++; }
System.out.println(count);
}

例子三

// 计算func3的时间复杂度?
void func3(int N, int M) {
int count = 0;
for (int k = 0; k < M; k++) {
   count++; }
for (int k = 0; k < N ; k++) {
   count++; }
System.out.println(count);
}

例子四

// 计算func4的时间复杂度?
void func4(int N) {
int count = 0;
for (int k = 0; k < 100; k++) {
   count++; }
System.out.println(count);
}

例子五

// 计算bubbleSort的时间复杂度?
void bubbleSort(int[] array) {
   for (int end = array.length; end > 0; end--) {
       boolean sorted = true;
       for (int i = 1; i < end; i++) {
           if (array[i - 1] > array[i]) {
            Swap(array, i - 1, i);
               sorted = false;
           }
       }
       if (sorted == true) {
           break;
       }
   }
}

例子六

// 计算binarySearch的时间复杂度?
int binarySearch(int[] array, int value) {
   int begin = 0;
   int end = array.length - 1;
   while (begin <= end) {
       int mid = begin + ((end-begin) / 2);
       if (array[mid] < value)
           begin = mid + 1;
       else if (array[mid] > value)
           end = mid - 1;
       else
           return mid;
   }
   return -1; }

例子七

// 计算阶乘递归factorial的时间复杂度?
long factorial(int N) {
 return N < 2 ? N : factorial(N-1) * N; }

空间复杂度

空间复杂度是对一个算法在运行过程中 临时占用存储空间大小的量度 。空间复杂度不是程序占用了多少 bytes的空间,因为这个也没太大意义,所以空间复杂度算的是变量的个数(额外变量个数)。空间复杂度计算规则基本跟时间复杂度 类似。也使用 大 O 渐进表示法 。

例子一

// 计算bubbleSort的空间复杂度?
void bubbleSort(int[] array) {
for (int end = array.length; end > 0; end--) {
     boolean sorted = true;
     for (int i = 1; i < end; i++) {
         if (array[i - 1] > array[i]) {
             Swap(array, i - 1, i);
             sorted = false;
         }
     }
     if (sorted == true) {
         break;
     }
 }
}

例子二

// 计算fibonacci的空间复杂度?
int[] fibonacci(int n) {
long[] fibArray = new long[n + 1];
fibArray[0] = 0;
fibArray[1] = 1;
for (int i = 2; i <= n ; i++) {
  fibArray[i] = fibArray[i - 1] + fibArray [i - 2];
 }
return fibArray;
}

例子三

// 计算阶乘递归Factorial的空间复杂度?
long factorial(int N) {
 return N < 2 ? N : factorial(N-1)*N;
 }

小结

这篇文章讲的都是一些简单的时间复杂度和空间复杂度的计算,如果有什么不正确的地方,欢迎大家指出来。

到此这篇关于Java数据结构通关时间复杂度和空间复杂度的文章就介绍到这了,更多相关Java时间复杂度 内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • Java算法之时间复杂度和空间复杂度的概念和计算

    一.算法效率 算法效率分析分为两种:第一种是时间效率,第二种是空间效率.时间效率被称为时间复杂度,而空间效率被称作空间复杂度. 时间复杂度主要衡量的是一个算法的运行速度,而空间复杂度主要衡量一个算法所需要的额外空间. 在计算机发展的早期,计算机的存储容量很小.所以对空间复杂度很是在乎.但是经过计算机行业的迅速发展,计算机的存储容量已经达到了很高的程度.所以我们如今已经不需要再特别关注一个算法的空间复杂度.因为现在的内存不像以前那么贵,所以经常听到过牺牲空间来换取时间的说法 二.时间复杂度 2.1

  • Java 精炼解读时间复杂度与空间复杂度

    目录 前言: 一.算法效率 二.时间复杂度 1.时间复杂度概念 2.大O的渐进表示法 计算时间复杂度 三.空间复杂度 总结: 前言: 所谓的复杂度就是衡量算法的效率,衡量算发效率又分为两种,一种叫做时间复杂度,一种叫做空间复杂度. 一.算法效率 算法效率分析分为两种:第一种是时间效率,第二种是空间效率.时间效率被称为时间复杂度,而空间效率被 称作空间复杂度. 时间复杂度主要衡量的是一个算法的运行速度,而空间复杂度主要衡量一个算法所需要的额 外空间,在计算机发展的早期,计算机的存储容量很小.所以对

  • Java时间复杂度、空间复杂度的深入详解

    目录 算法效率 时间复杂度 什么是时间复杂度 推导大 O 阶的方法 算法情况 计算冒泡排序的时间复杂度 计算二分查找的时间复杂度 计算阶乘递归的时间复杂度 计算斐波那契递归的时间复杂度 空间复杂度 计算冒泡排序的空间复杂度 计算斐波那契数列的空间复杂度(非递归) 计算阶乘递归Factorial的时间复杂度 总结 算法效率 在使用当中,算法效率分为两种,一是时间效率(时间复杂度),二是空间效率(空间复杂度).时间复杂度是指程序运行的速度.空间复杂度是指一个算法所需要的额外的空间. 时间复杂度 什么

  • Java 数据结构之时间复杂度与空间复杂度详解

    目录 算法效率 时间复杂度 什么是时间复杂度 推导大 O 阶的方法 算法情况 计算冒泡排序的时间复杂度 计算二分查找的时间复杂度 计算阶乘递归的时间复杂度 计算斐波那契递归的时间复杂度 空间复杂度 计算冒泡排序的空间复杂度 计算斐波那契数列的空间复杂度(非递归) 计算阶乘递归Factorial的时间复杂度 算法效率 在使用当中,算法效率分为两种,一是时间效率(时间复杂度),二是空间效率(空间复杂度).时间复杂度是指程序运行的速度.空间复杂度是指一个算法所需要的额外的空间. 时间复杂度 什么是时间

  • Java 关于时间复杂度和空间复杂度的深度刨析

    目录 1.算法效率 2.时间复杂度 2.1时间复杂度的概念 2.2大O的渐进表示法 2.3常见时间复杂度计算 2.3.1常用的时间复杂度量级 2.3.2常见示例举例 2.3.2示例答案及分析 3.空间复杂度 1.算法效率 算法效率分析分为两种:第一种是时间效率,第二种是空间效率.时间效率被称为时间复杂度,而空间效率被称作空间复杂度. 时间复杂度主要衡量的是一个算法的运行速度,而空间复杂度主要衡量一个算法所需要的额外空间 如今我们更关注的是时间复杂度,而对空间复杂度已不再关注. 2.时间复杂度 2

  • Java 数据结构与算法系列精讲之时间复杂度与空间复杂度

    目录 概述 算法的衡量标准 时间复杂度 最优时间复杂度 平均时间复杂度 最坏时间复杂度 O(1) O(n) O(n^2) O(logN) 空间复杂度 O(1) O(n) 概述 从今天开始, 小白我将带大家开启 Jave 数据结构 & 算法的新篇章. 算法的衡量标准 当我们需要衡量一个算法的的优越性, 通常会使用时间复杂度 (Time Complexity) 和空间复杂度 (Space Complexity) 来衡量. 时间复杂度 时间复杂度 (Time Complexity) 通常用 O(n)

  • Java数据结构通关时间复杂度和空间复杂度

    目录 算法效率 时间复杂度 空间复杂度 小结 算法效率 算法效率分析分为两种:第一种是时间效率,第二种是空间效率.时间效率被称为时间复杂度,而空间效率被 称作空间复杂度. 时间复杂度主要衡量的是一个算法的运行速度,而空间复杂度主要衡量一个算法所需要的额 外空间,在计算机发展的早期,计算机的存储容量很小.所以对空间复杂度很是在乎(以前是以时间换空间).但是经过计算机行业的 迅速发展,计算机的存储容量已经达到了很高的程度.所以我们如今已经不需要再特别关注一个算法的空间复 杂度(现在是以空间换时间).

  • C语言数据结构通关时间复杂度和空间复杂度

    目录 1.时间复杂度: 1.常数阶 2.线性阶 3.对数阶 4.平方阶 2.算法空间复杂度 算法的时间复杂度和空间复杂度 1.时间复杂度: 首先,为什么会有这个概念的出现呢? 原来啊,在进行算法分析时,语句总的执行次数T(n)是关于问题规模n的函数,进而分析T(n)随n的变化情况并确定T(n)的数量级.算法的时间复杂度,也就是算法的时间量度,记作T(n) = O(f(n)).它表示随问题规模n的增大,算法执行时间的增长率和f(n)的增长率相同,称作算法的渐进时间复杂度,简称为时间复杂度,其中f(

  • C语言数据结构时间复杂度及空间复杂度简要分析

    目录 一.时间复杂度和空间复杂度是什么? 1.1算法效率定义 1.2时间复杂度概念 1.3空间复杂度概念 二.如何计算常见算法的时间复杂度和空间复杂度 2.1时间复杂度计算 2.2空间复杂度计算 2.3快速推倒大O渐进表达法 三.一些特殊的情况 总结 一.时间复杂度和空间复杂度是什么? 1.1算法效率定义 算法效率分为两种,一种是时间效率--时间复杂度,另一种是空间效率--空间复杂度 1.2时间复杂度概念 时间复杂度,简言之就是你写一个代码,它解决一个问题上需要走多少步骤,需要花费多长时间.打个

  • java数据结构与算法之插入排序详解

    本文实例讲述了java数据结构与算法之插入排序.分享给大家供大家参考,具体如下: 复习之余,就将数据结构中关于排序的这块知识点整理了一下,写下来是想与更多的人分享,最关键的是做一备份,为方便以后查阅. 排序 1.概念: 有n个记录的序列{R1,R2,.......,Rn}(此处注意:1,2,n 是下表序列,以下是相同的作用),其相应关键字的序列是{K1,K2,.........,Kn}.通过排序,要求找出当前下标序列1,2,......,n的一种排列p1,p2,........pn,使得相应关键

随机推荐