首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往
您找到你想要的搜索结果了吗?
是的
没有找到

空间时间的思路很妙

还有一个更简单高效的答案,就是查表法,利用空间换取时间。...但是问题来了,一个 32 位的计算机可以表示的整数有 2 的 32 次方个,每个整数假如是 4 字节,如果要把这些数都存在表里,至少需要 16 GB的内存空间,如果是 64 位,则需要的内存不小于 67108864...当然不是,我们可以只保留 16 位整数的缓存表,只需要 256 KB左右的内存空间,然后将 32 位或 64 位的整数拆成每 16 位一组,这样 32 位的只需要查 2 次,64 位的只需要查 4 次。...,从理论上上看,32 位的缓存表查询次数更少,应该更快,实际上,计算机的 cpu 和内存之间还有一个高速缓存,高速缓存的空间非常小,通常只有几兆,计算机往往需要把内存先往高速缓存中搬运,然后做相应的处理

76930

【排序算法】经典空间时间基数排序

源代码 git 仓库 ‘ 数据结构代码地址 代码Git 仓库地址 目录 前言 基数排序 基数排序(桶排序)介绍 基数排序基本思想 动图演示 代码思路实验 速度测试 基数排序的说明: 基数排序 经典空间时间的思想流排序算法...,金典的空间时间的算法 第二轮 最后 动图演示 代码思路实验 要求:将数组 {53, 3, 542, 748, 14, 214} 使用基数排序, 进行升序排序 package com.hyc.DataStructure.sort...名明确,基数排序是使用空间时间的经典算法 int[][] bucket = new int[10][arr.length]; //为了记录每个桶中,实际存放了多少个数据...我们简单计算一下用来多少内容 8000000 * 11 * 4 / 1024 / 1024 / 1024 =1G 从公式可以看出我们排序八百万 使用到了1g的内存,从各方面都可以看出,基数排序是经典的空间时间的算法...基数排序是经典的空间时间的方式,占用内存很大, 当对海量数据排序时,容易造成 OutOfMemoryError 。 基数排序时稳定的。

58630

常见的算法优化套路,用空间时间

今天我们来聊聊算法当中非常常见的一种优化思路,以空间时间。 这里的空间指的是空间复杂度,时间指的是时间复杂度。空间时间即是指牺牲一定的空间复杂度来换取更低的时间复杂度,来保证程序的运行效率。...很多时候,更大的存储空间就是更高性能的代价。不过好在现在内存的价格越来越便宜,而程序效率越来越重要,空间时间的这个操作也就越来越有价值。...空间时间是很多算法和数据结构的出发点,我们当然不可能在一篇文章当中穷尽所有的应用场景。但至少我们可以理解它的运作原理,对于这样的技巧或者策略有一定的认知。...我们利用了数组下标的有序性来进行排序,这本质上就是一种空间时间的思路。 记忆化和缓存 我们再来看一个经典的例子,在一些递归问题当中,可能会出现一些子问题被反复求解导致冗余的问题。...关于空间时间的具体用法我们还会在之后的文章当中遇到,这里就不过多发散了。如果有什么想说的,欢迎在下方评论。

2.2K20

LeetCode 例题精讲 | 18 前缀和:空间时间的技巧

有些时候,我们可以通过增加空间占用的方式减少算法的运行时间,这便是空间时间。 动态规划就是一类空间时间的算法。动态规划通过保存所有子问题的计算结果,可以避免子问题的重复计算。...这种方法的代价是 DP 数组 占用了较多的空间。 前缀和同样也是一种空间时间的技巧,只不过我们使用的不是 DP 数组,而是「前缀和数组」。 那么,究竟什么是前缀和呢?...我们来看看不同的解法的时间、空间复杂度有何区别。 解法一:暴力法 image.png ?...for (int k = i; k <= j; k++) { sum += nums[k]; } return sum; } image.png 解法二:空间时间...解法二:空间时间 private int[][] res; // 预处理阶段 public NumArray(int[] nums) { int n = nums.length; res

1.1K20
领券