时间换空间_时间换空间去解决问题 - CSDN
精华内容
参与话题
  • 空间换时间和时间换空间

    千次阅读 2018-06-17 15:22:55
    考虑实际情况,可能会用“空间换时间”或者用“时间换空间”。以数组排序为例。很明显,冒泡排序,通过新增一个中间变量,用空间换时间,执行速度快。而异或运算没有引入新的变量。package com.asin.java.csdn; ...
    算法有两个指标:运行时间、内存消耗。
    考虑实际情况,可能会用“空间换时间”或者用“时间换空间”。
    以数组排序为例。很明显,冒泡排序,通过新增一个中间变量,用空间换时间,执行速度快。而异或运算没有引入新的变量。
    package com.asin.java.csdn;  
      
    import java.util.Arrays;  
      
    public class AlgorithmCompare {  
        public static void main(String[] args) {  
      
            int[] num = { 2, 5, 1, 7, 3, 8, 6, 9, 0 };  
      
            long start = System.nanoTime();  //纳秒  
      
            // sortThird(num); // 191999  
            bubbleSort(num);   //   5531  
      
            long end = System.nanoTime();  
      
            System.out.println(end - start);  
        }  
      
        /** 
         * 冒泡排序,空间换时间 
         */  
        public static void bubbleSort(int[] a) {  
            int n = a.length;  
            for (int i = 0; i < n - 1; i++) {  
                for (int j = 0; j < n - 1; j++) {  
                    if (a[j] > a[j + 1]) {  
                        int temp = a[j];  
                        a[j] = a[j + 1];  
                        a[j + 1] = temp;  
                    }  
                }  
            }  
        }  
      
        /** 
         * 异或运算,时间换空间 
         */  
        private static void sortThird(int[] num) {  
            for (int i = 1; i < num.length; i++) {  
                int j = i;  
                while (true) {  
                    if (j > 0 && num[j] < num[j - 1]) {  
                        // change  
                        num[j] = num[j] ^ num[j - 1];  
                        num[j - 1] = num[j] ^ num[j - 1];  
                        num[j] = num[j] ^ num[j - 1];  
                        j--;  
                    } else {  
                        break;  
                    }  
                }  
            }  
            System.out.println("sortThird:" + Arrays.toString(num));  
        }  
    }  

    展开全文
  • 空间换时间的算法

    2020-10-25 10:21:33
    空间换时间的算法 大多算法考试都会有这个要求,就是在规定的时间复杂度内得到求解,这种情况下,一般多是需要复合遍历的内容,也即是时间复杂度在O(N2)和O(N3)等算法时间较高的情况下,此篇内容就是探讨一下一般...

    以空间换时间的算法

    大多算法考试都会有这个要求,就是在规定的时间复杂度内得到求解,这种情况下,一般多是需要复合遍历的内容,也即是时间复杂度在O(N2)和O(N3)等算法时间较高的情况下,此篇内容就是探讨一下一般的有哪些是以空间换时间的算法
    LCP18.早餐组合

    小扣在秋日市集选择了一家早餐摊位,一维整型数组 staple 中记录了每种主食的价格,一维整型数组 drinks 中记录了每种饮料的价格。小扣的计划选择一份主食和一款饮料,且花费不超过 x 元。请返回小扣共有多少种购买方案。
    (注意:答案需要以 1e9 + 7 (1000000007) 为底取模,如:计算初始结果为:1000000008,请返回 1)
    示例:
    输入:staple = [10,20,5], drinks = [5,5,2], x = 15
    输出:6
    题目分析,显然遍历两次轻松的到题解,但复杂度为O(mn),但这题的要求就是时间复杂度降低到O(m+n),

    思路一,二分查找
    如果对第一个数组排序,则需要mlogm+nlogm = (m+n)logm
    如果对第二个数组排序,则需要nlogn+mlogn = (m+n)logn
    所以我们只需要对长度较小的数组排序即可,总的时间复杂度为(m+n)log(min(m,n))

    def helper(self,v,n):
        if v[-1] <= n: return len(v)
        l,r = 0,len(v)-1
        while l < r:
            mid = (l+r) // 2
            if v[mid] <= n: l = mid+1
            else: r = mid
        return l
        
    def breakfastNumber(self, staple: List[int], drinks: List[int], x: int) -> int:
        res = 0
        if len(staple) <= len(drinks):
            staple.sort()
            for n in drinks:
                res = (res+self.helper(staple,x-n)) % 1000000007
        else:
            drinks.sort()
            for n in staple:
                res = (res+self.helper(drinks,x-n)) % 1000000007
        return res
    

    思路二,桶排序算法,时间复杂度为O(m+n)

    class Solution:
        def breakfastNumber(self, staple: List[int], drinks: List[int], x: int) -> int:
            ans = 0
            arr = [0 for i in range(x+1)]
            P = 1000000007
            for sta in staple:
                if sta<x:
                    arr[sta] +=1
            # 因为staple内的值必须是小于x的,这样才能算上饮料,一旦找到sta<x的情况,
            # 那么在对应的x中的位置就+1,显示其出现的次数
            for i in range(2,x):
                arr[i] +=arr[i-1]
            # arr[i] 第i个元素表示食物里面价格小于等于i的个数
            # 这一步的作用就是让1-15内的值 确定每个食物可以接受多少个小于其值的饮料的值
            for drink in drinks:
                It = x - drink
                if It<=0:
                    continue
                ans +=arr[It]
            ans = ans%P
            return ans
            # 此解法分两步,找到1-15(既X内,食物价格出现的次数)
            # 第二步生成一个匹配表,这个表内的每个元素,表示食物内价格小于或的等于当前价格的个数,所以要用累加法,从小的开始向前累加。
            # 最后x-drinks得到的值 既可以直接去对照表内查找 剩余的钱可以买到的食物的个数。
            # 时间复杂度为O(m+n)最快时间复杂度
    

    以时间换空间的算法

    展开全文
  • 时间换空间

    2007-10-23 12:15:26
    今天在开发中,偶然发现以前前辈留下的一段代码,不长不复杂,可仔细分析,却有点意思。 int a,b,c; int value; if(vlaue &gt;= 4) {  a = 1;  value = vlaue - 4; } else {  a = 0;...i...

    今天在开发中,偶然发现以前前辈留下的一段代码,不长不复杂,可仔细分析,却有点意思。

    int a,b,c;
    int value;
    if(vlaue >= 4)
    {
     a = 1;
     value = vlaue - 4;
    }
    else
    {
     a = 0;
    }
    if(value  >= 2)
    {
     b = 1;
     value = value - 2;
    }
    else
    {
     b = 0
    }
    if(value  >= 1)
    {
     c = 1;
     value = value - 1;
    }
    else
    {
     c = 0
    }

    有value一个值,根据此值判断另外多个值的情况。
    典型的以时间换空间的问题。
    可以值储存一个value值,来替代要储存的多个值:a,b,c。
    当然,多个值也只能够有true flase两种情况。

    相应的原理可以用二进制来表示,如下:

    1  1  1  ------- 7

    1  1  0 -------  6

    1  0  1  ------- 5

    1  0  0  ------- 4

    0  1  1  ------- 3

    0  1  0  ------- 2

    0  0  1  ------- 1

    展开全文
  • 有这样一个应用: 一个向外推送帖子的网站,需要记录帖子都为哪些用户浏览过。怎么设计? ...为每一个帖子开辟一个8M的存储空间,按照用户的id记录用户是否阅读过,以0表示false,1表示true。...

    有这样一个应用:

    一个向外推送帖子的网站,需要记录帖子都为哪些用户浏览过。怎么设计?

     

    设计一(很粗糙的实现)

    将帖子和用户做多对多关联,关联上了就是阅读过了。

    那么问题来了,当用户数达到千万级别,帖子数达到万级,那将是很可怕的数量。

     

    设计二(一位资深人士给的做法)

    为每一个帖子开辟一个8M的存储空间,按照用户的id记录用户是否阅读过,以0表示false,1表示true。当然用户的id是从1开始自增长的。

     

    我想说这两方法都太浪费存储资源了

    关键是记录用户的最后访问时间,帖子的发布时间。

    只要将用户的最后登陆时间和当前时间之间发布的帖子塞进用户的未读列表即可(可以在用户登陆的同时处理),用户每阅读一篇即可从未读列表中删除

     

    如此,统计一篇帖子有哪些人未阅读过

    最后登录时间早于帖子发布时间的 + 时间晚于帖子发布时间,且阅读列表中有这篇帖子的

     

    统计一篇帖子有哪些人阅读过

    时间晚于帖子发布时间,且阅读列表中没有这篇帖子的

     

    这里的时间换空间就是消费计算机的运算时间换取存储的节约

    展开全文
  • 空间时间转换

    千次阅读 2018-07-27 16:29:29
    空间和时间之间的转换无非就两种方式即:时间换空间,空间换时间。 当年蒋介石就完成过空间换时间,以大量的土地换取自己喘息的时间。 在实际开发中时间 = 运行时间,空间 = 运行内存,所以空间和时间的转换其实也...
  • 代码时间换空间以及空间换时间

    千次阅读 2016-05-30 17:57:07
    void swap(int a, int b) ...//根据以上的题意解释一下以时间换空间,和以空间换时间 第一个,用空间换时间,swap中定义了c,就是在内存中又开辟了一个int内存空间,然后一次swap需要进行三次赋
  • 时间换空间 由于系统资源是有限的,为了在有限的资源内,达成某些特定的性能目标,时间换空间或者空间换时间的方法。 时间换空间通常用于嵌入式设备,或者内存、硬盘空间不足的情况,通过使用牺牲CPU的方式,获得...
  • 性能优化:空间换时间

    千次阅读 热门讨论 2016-03-04 16:33:29
    问题背景  在程序开发过程中,我们对于数据的处理,会有一些校验。   校验分为两种:简单校验和复杂校验。 ...这种校验,可以说几乎不耗时的。所以也没必要在这里做优化。   对于复杂的校验,需要进行联合查询,...
  • 算法的好坏有两个指标:需要的内存空间(可以 理解为运行代码需要的内存空间),代码运行的时间(可以简单的理解为代码需要执行的步数)程序的设计要不就是时间换空间,要不就是用空间去换时间。并且时间和空间是...
  • 空间换时间经典算法

    千次阅读 2010-11-13 20:33:00
    以前看过一篇文章“优化C代码常用的几招”,作者提到的第一招就是“以空间换时间”,还举了一个例子,由于比较经典,引用一下:计算机程序中最大的矛盾是空间时间的矛盾,那么,从这个角度出发逆向思维来考虑程序...
  • 小猪的数据结构辅助教程——1.数据结构与算法绪论标签(空格分隔...了解空间复杂度的概念,闰年表空间换时间的例子~ 1.什么是数据结构?2.算法的叙述3.时间复杂度计算的简单示例数据结构预算法——时间复杂度分析实例
  • 一、常用排序算法的时间复杂度和空间复杂度表格 二、特点 1.归并排序: (1)n大时好,归并比较占用内存,内存随n的增大而增大,但却是效率...(3)以时间换空间:网上很多blog分享空间复杂度只有O(1)的归并排序法
  • 【Android】性能优化

    万次阅读 2020-01-13 09:36:12
    时间换空间: 如拷贝文件时new一个字节数组当缓冲器,即byte[] buffer = new byte[1024]。 为什么只new一个1024个字节的数组呢,new一个更大的字节数组不是一下就把文件拷贝完了么?这么做就是为了牺牲时间节...
  • 关于程序性能优化的方向

    万次阅读 2017-11-06 16:41:21
    程序性能调优------------------------------------------------------------1、性能调优层次a.设计调优;b.代码调优;c.jvm调优(如:java);...时间换空间,空间换时间(如:cpu,磁盘等处理转换);
  • 算机在完成一个任务的时候有两个指标,时间和所有内存(也就是空间)。这两者是负相关的。也就是说,当你设计一个特定程序时,你可以选择使用更多的内存,这样可以达到提高程序运行速度的目的,也就是减少程序运行...
  • mysql 以空间换时间专研

    千次阅读 2020-07-02 13:16:00
    提升mysql数据库执行效率是个永远的难题,...一、增加空间换时间 数据表 CREATE TABLE `sms` ( `id` bigint(20) NOT NULL AUTO_INCREMENT COMMENT 'id', `user_id` bigint(20) NOT NULL COMMENT '用户id', `tel` c
  • 算法的时间复杂度和空间复杂度计算

    万次阅读 多人点赞 2018-09-27 20:22:44
    1、算法时间复杂度 1.1算法时间复杂度的定义:  在进行算法分析时,语句总的执行次数T(n)是关于问题规模n的函数,进而分析T(n)随n的变化情况并确定T(n)的数量级。算法的时间复杂度,也就是算法的时间量度,记作...
  • 磁盘和目录空间 进程信息 文章目录系统信息相关命令1.时间和日期1.1 date 时间1.2 cal 日历02.磁盘信息03.进程信息 1.时间和日期 1.1 date 时间 第一步: 显示当前时间 # 显示时间 date # 按照指定格式显示时间 ...
  • 关于计算时间复杂度和空间复杂度

    万次阅读 多人点赞 2017-04-14 09:26:37
    相信学习编程的同学,或多或少都接触到算法的时间复杂度和空间复杂度了,那我来讲讲怎么计算。  常用的算法的时间复杂度和空间复杂度 一,求解算法的时间复杂度,其具体步骤是:  ⑴ 找出算法中的基本语句;  ...
  • 在排序算法中快速排序的效率是非常高的,但是还有种排序算法的效率可以与之媲美,那就是归并排序;归并排序和快速排序有那么点异曲同工之妙,快速排序:是先把数组粗略的排序成两个子数组,然后递归再粗略分两个子...
1 2 3 4 5 ... 20
收藏数 876,204
精华内容 350,481
关键字:

时间换空间