精华内容
下载资源
问答
  • Hash表的时间复杂度为什么是O(1)? 从hash表的结构来看: hash表是基于数组和链表来实现的,存储数据是使用的是余数法,即使用hash表的长度(8)对key的hashCode(101)求余,余数(5)就是数组的下标。 但是,余数法存在...

    Hash表的时间复杂度为什么是O(1)?

    从hash表的结构来看:

    hash表是基于数组链表来实现的,存储数据是使用的是余数法,即使用hash表的长度(8)对key的hashCode(101)求余,余数(5)就是数组的下标。
    在这里插入图片描述

    但是,余数法存在一个问题,就是不同key可能存在相同的下标,比如:101%8=5和109%8=5得到相同的下标(5),这就造成了hash冲突。

    为了解决hash冲突,常用的方法就是链表法,hash表将冲突的下标退化成一条链表,链表的时间复杂度为O(N),所以hash表单的时间复杂度就是O(1)

    在这里插入图片描述
    参考:
    https://blog.csdn.net/weixin_44617285/article/details/105507811
    https://blog.csdn.net/YYQ_QYY/article/details/105992427

    展开全文
  • 本文是学习李智慧在极客时间的《后端技术面试38讲》课程内容的收获 这个问题看起来是对哈希表这一数据结构的理解,但其实是对其实现方式所使用的基本知识的理解,体现了对基础知识的深刻理解和知识结构的体系化。

    本文是学习李智慧在极客时间的《后端技术面试38讲》课程内容的收获

    这个问题看起来是对哈希表这一数据结构的理解,但其实是对其实现方式所使用的基本知识的理解,很好的反映了新技术都是建立在基础技术上这一理念。

    标准答案

            Hash表对外暴露的功能是通过Key值,在O(1)的时间复杂度内找到对应的Value(Key是去重的)。对应的唯一性是通过<Key, Hash值>  + <Hash值, 内存地址>保证。有意思的地方主要是看是通过什么样的方法去保证<Hash值, 内存地址>的唯一性和时间复杂度

    1. Key值---》Hash函数---》Hash值(时间复杂度为O(1))
    2. 通过Hash值定位Value

            步骤1的时间复杂度是hash函数保证,重要的是步骤二的时间复杂度也要为O(1),我知道的就是Hash表维护一个一维数组,通过将Hash值对数组长度取余,得到一个[0, 数组长度)的范围值,正好对应数组下标,通过数组下标可以在O(1)的时间复杂度内得到Value。会有取余后下标相同的情况,Value跟在之前的Value后面,遍历找到对应的元素。数组元素就变为链表首地址

    从基础知识推理Hash的实现

    这是一个 1 + 1 > 2的过程,面试碰到这一题如果能推出来真的是天才。但是这个分析过程帮助我们更能理解基础知识

    1. 底层存储中,<内存地址, Value>是一一对应的,现在有Hash函数来保证<Key, Hash值>是一一对应,理想化的话那么我们只要保证<Hash值, 内存地址>是一一对应的(这里只要保证此映射是O(1)的,就能保证Hash表的O(1))
    2. 理想化的情况要涉及到对内存的操作,不太现实,尽量利用已有的数据结构
    3. 数组访问元素是通过内存地址 = 数组首地址 + 元素下标 * 元素占位占内存个数来访问,这个操作是O(1),理想情况那只要保证<Hash值, 数组下标>是唯一的,并且映射过程是O(1)
      1. 数组的实际数据是分配在堆中(连续的内存块),栈帧中(函数调用底层结构)能计算数组元素位置需要数组首地址,这就反映出数组在声明时将数组内存首地址保存到了栈帧中,就是函数中的数组名
    4. 如果碰到取余映射相同,就跟在后面形成一张链表

    利用Hash值取余的话,极端情况下会退化成一张链表,通过Key查找一个Value时间复杂度就变为O(n)(步骤1-3的时间复杂度不变,最后遍历查找链表的时间为O(n))。要保证Hash表的时间复杂度,就是<Hash值, 内存地址>的映射过程时间复杂度尽量低。盗张图,这张图并不是Hash表的全部,Hash表是一个类,包含了上述的流程,实现了相关需求,表只是一个抽象的概念。图中只是这个类中数组部分的数据结构

    展开全文
  • 基础算法冒泡排序冒泡排序的三种方式(不断优化)看个小例题选择排序插入排序 ... for (int i = 0; i < arr.length - 1; i++) { for (int j = 0; j < arr.length - 1 - i; j++) { if (arr[j] > arr[j + 1]

    冒泡排序

    冒泡排序的三种方式(不断优化)

    /*常规冒泡*/
    public static void bubbleSort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = 0; j < arr.length - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    // 如果左边的数大于右边的数,则交换,保证右边的数字最大
    				int temp = arr[j + 1];
    				arr[j + 1] = arr[j];
    				arr[j] = temp;
                }
            }
        }
    }
    

    改进一:

    public static void bubbleSort(int[] arr) {
        // 初始时 swapped 为 true,否则排序过程无法启动
        boolean swapped = true;
        for (int i = 0; i < arr.length - 1; i++) {
            // 如果没有发生过交换,说明剩余部分已经有序,排序完成
            if (!swapped) break;
            // 设置 swapped 为 false,如果发生交换,则将其置为 true
            swapped = false;
            for (int j = 0; j < arr.length - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    // 如果左边的数大于右边的数,则交换,保证右边的数字最大
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    // 表示发生了交换
                    swapped = true;
                }
            }
        }
    }
    
    

    改进二:

    public static void bubbleSort(int[] arr) {
        boolean swapped = true;
        // 最后一个没有经过排序的元素的下标
        int indexOfLastUnsortedElement = arr.length - 1;
        // 上次发生交换的位置
        int swappedIndex = -1;
        while (swapped) {
            swapped = false;
            for (int i = 0; i < indexOfLastUnsortedElement; i++) {
                if (arr[i] > arr[i + 1]) {
                    // 如果左边的数大于右边的数,则交换,保证右边的数字最大
                    int temp = arr[i];
                    arr[i] = arr[i + 1];
                    arr[i + 1] = temp;
                    // 表示发生了交换
                    swapped = true;
                    // 更新交换的位置
                    swappedIndex = i;
                }
            }
            // 最后一个没有经过排序的元素的下标就是最后一次发生交换的位置
            indexOfLastUnsortedElement = swappedIndex;
        }
    }
    
    

    看个小例题

    在这里插入图片描述

    class Solution {
        public int[] getLeastNumbers(int[] arr, int k) {
            int last_swap_index = arr.length - 1;
            int swap_index = -1;
            int swap = 1;
            int[] ans=new int[k];
            while(swap==1){
                swap = 0;
                for(int i=0;i<arr.length;i++){
                    for(int j =0;j<arr.length-1-i;j++){
                        if(arr[j]>arr[j+1]){
                            int temp;
                            temp = arr[j+1];
                            arr[j+1] = arr[j];
                            arr[j] = temp;
                            swap = 1;
                            swap_index = j;
                        }
                    }
                }
                last_swap_index = swap_index;
            }
            for(int i=0;i<k;i++){
                ans[i] = arr[i];
            }   
            return ans;  
        }
    }
    

    既然是讲冒泡,就用冒泡来写一下,写的过程中发现,传统冒泡在执行时会超时,只能用第三种冒泡。又用了Python3 来写了一下,完美超时。
    在这里插入图片描述

    class Solution {
        public void moveZeroes(int[] nums) {
            int j = 0;
            for(int i =0; i < nums.length; i++){
                if (nums[i] != 0){
                    if(i > j){
                        nums[j] = nums[i];
                        nums[i] = 0;
                    }
                    j++;
                }
            }
        }
    }
    

    可用冒泡排序做,但是没必要,,,快慢指针更舒服。

    选择排序

    选择排序具体步骤
    「选择排序」每一轮都选取「未排定的部分」的最小元素,然后将它 交换 到「未排定的部分」的第 1 个位置。下面我们通过一个具体的例子,说明选择排序的执行步骤。

    • 例:将数组 [8, 3, 9, 6, 4, 1, 5, 2, 10, 7] 升序排序。

    • 首先经过一次扫描,通过逐个比较,找到整个数组中最小的元素 1,把它交换到这个数组的开头,交换以后,1 就呆在了最终应该在的位置;

    • 接下来,继续扫描未排定的部分,选出最小的元素 2,把它交换到未排定的部分的第 1 个位置,这个位置就是 2 这个元素最终应该呆的位置;

    • 接下来的操作,我们就不赘述了。直到「未排定的部分」只剩下一个元素,此时,我们就不用比较了,它一定是整个数组中最大的那个元素。到此为止,我们就得到了原始数组的升序排序结果。

    import java.util.Arrays;
    
    public class Solution {
    
        // 「力扣」第 912 题:排序数组
    
        public int[] sortArray(int[] nums) {
            int len = nums.length;
            // 最后一轮只有一个元素,一定是最大的元素,因此写 i < len - 1
            for (int i = 0; i < len - 1; i++) {
                // 在 [i + 1, len - 1] 区间里选择最小的元素的下标
                int minIndex = i;
                for (int j = i + 1; j < len; j++) {
                    if (nums[j] < nums[minIndex]) {
                        minIndex = j;
                    }
                }
                swap(nums, minIndex, i);
    
                // 调试语句,检查排序过程是否正确
                System.out.println(Arrays.toString(nums));
            }
            return nums;
        }
    
        private void swap(int[] nums, int index1, int index2) {
            int temp = nums[index1];
            nums[index1] = nums[index2];
            nums[index2] = temp;
        }
    
        public static void main(String[] args) {
            int[] nums = {8, 3, 9, 6, 4, 1, 5, 2, 10, 7};
            Solution solution = new Solution();
            int[] res = solution.sortArray(nums);
            System.out.println(Arrays.toString(res));
        }
    }
    

    时间复杂度:O(N^2)
    选择排序的特点:

    • 交换次数最少
    • 运行时间与输入无关

    插入排序

    未完

    展开全文
  • 一、算法的时间复杂度定义在...它表示随问题n的增大,算法执行时间的增长率和f(n)的增长率相同,称作算法的渐进时间复杂度,简称为时间复杂度。其中,f(n)是问题规模n的某个函数。这样用大写O()来体现算法时间复杂度...

    一、算法的时间复杂度定义

    在进行算法分析时,语句总的执行次数T(n)是关于问题规模n的函数,进而分析T(n)随n的变化情况并确定T(n)的数量级。算法的时间复杂度,也就是算法的时间量度。记作:T(n)=O(f(n))。它表示随问题n的增大,算法执行时间的增长率和f(n)的增长率相同,称作算法的渐进时间复杂度,简称为时间复杂度。其中,f(n)是问题规模n的某个函数。

    这样用大写O()来体现算法时间复杂度的记法,我们称之为大0记法。

    二、推导大O阶方法

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

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

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

    三、推导示例

    1、常数阶

    首先顺序结构的时间复杂度。下面这个算法,是利用高斯定理计算1,2,……n个数的和。

    1 int sum = 0, n = 100; /*执行一次*/

    2

    3 sum = (1 + n) * n / 2; /*执行一次*/

    4

    5 printf("%d",sum); /*执行一次*/

    这个算法的运行次数函数是f (n)  =3。 根据我们推导大0阶的方法,第一步就是把常数项3 改为1。在保留最高阶项时发现,它根本没有最高阶项,所以这个算法的时间复杂度为0(1)。

    另外,我们试想一下,如果这个算法当中的语句 sum = (1+n)*n/2;有10 句,则与示例给出的代码就是3次和12次的差异。这种与问题的大小无关(n的多少),执行时间恒定的算法,我们称之为具有O(1)的时间复杂度,又叫常数阶。对于分支结构而言,无论是真,还是假,执行的次数都是恒定的,不会随着n 的变大而发生变化,所以单纯的分支结构(不包含在循环结构中),其时间复杂度也是0(1)。

    2、线性阶

    线性阶的循环结构会复杂很多。要确定某个算法的阶次,我们常常需要确定某个特定语句或某个语句集运行的次数。因此,我们要分析算法的复杂度,关键就是要分析循环结构的运行情况。

    下面这段代码,它的循环的时间复杂度为O(n), 因为循环体中的代码须要执行n次。

    1 inti;2

    3 for(i = 0; i < n; i++){4

    5 /*时间复杂度为O(1)的程序步骤序列*/

    6

    7 }

    3、对数阶

    如下代码:

    1 int count = 1;2

    3 while (count

    5 count = count * 2;6

    7 /*时间复杂度为O(1)的程序步骤序列*/

    8

    9 }

    由于每次count乘以2之后,就距离n更近了一分。 也就是说,有多少个2相乘后大于n,则会退出循环。 由2^x=n 得到x=logn。 所以这个循环的时间复杂度为O(logn)。

    4、平方阶

    下面例子是一个循环嵌套,它的内循环刚才我们已经分析过,时间复杂度为O(n)。

    1 inti, j;2

    3 for(i = 0; i < n; i++){4

    5   for(j = 0; j < n; j++){6

    7 /*时间复杂度为O(1)的程序步骤序列*/

    8

    9   }10

    11 }

    而对于外层的循环,不过是内部这个时间复杂度为O(n)的语句,再循环n次。 所以这段代码的时间复杂度为O(n^2)。

    如果外循环的循环次数改为了m,时间复杂度就变为O(mXn)。

    所以我们可以总结得出,循环的时间复杂度等于循环体的复杂度乘以该循环运行的次数。

    那么下面这个循环嵌套,它的时间复杂度是多少呢?

    1 inti, j;2

    3 for(i = 0; i < n; i++){4

    5   for(j = i; j < n; j++){ /*注意j = i而不是0*/

    6

    7   /*时间复杂度为O(1)的程序步骤序列*/

    8

    9   }10

    11 }

    由于当i=0时,内循环执行了n次,当i = 1时,执行了n-1次,……当i=n-1时,执行了1次。所以总的执行次数为:

    c0c70aa42dfc45c6ac8ecff0424636a3.png

    用我们推导大O阶的方法,第一条,没有加法常数不予考虑;第二条,只保留最高阶项,因此保留时(n^2)/2; 第三条,去除这个项相乘的常数,也就是去除1/2,最终这段代码的时间复杂度为O(n2)。

    从这个例子,我们也可以得到一个经验,其实理解大0推导不算难,难的是对数列的一些相关运算,这更多的是考察你的数学知识和能力。

    5、立方阶

    下面例子是一个三重循环嵌套。

    1 inti, j;2

    3 for(i = 1; i < n; i++)4

    5 for(j = 1; j < n; j++)6

    7 for(j = 1; j < n; j++){8

    9 /*时间复杂度为O(1)的程序步骤序列*/

    10

    11

    12

    13 }

    这里循环了(1^2+2^2+3^2+……+n^2) = n(n+1)(2n+1)/6次,按照上述大O阶推导方法,时间复杂度为O(n^3)。

    四、常见的时间复杂度

    常见的时问复杂度如表所示。5562fcfdebaf3e64e07934cfb5a49943.png

    常用的时间复杂度所耗费的时间从小到大依次是:5d036bbafa734d78590f0ca30a9aeda5.png

    我们前面已经谈到了。O(1)常数阶、O(logn)对数阶、O(n)线性阶、 O(n^2)平方阶等,像O(n^3),过大的n都会使得结果变得不现实。同样指数阶O(2^n)和阶乘阶O(n!)等除非是很小的n值,否则哪怕n 只是100,都是噩梦般的运行时间。所以这种不切实际的算法时间复杂度,一般我们都不去讨论。

    五、最坏情况与平均情况

    我们查找一个有n 个随机数字数组中的某个数字,最好的情况是第一个数字就是,那么算法的时间复杂度为O(1),但也有可能这个数字就在最后一个位置上待着,那么算法的时间复杂度就是O(n),这是最坏的一种情况了。

    最坏情况运行时间是一种保证,那就是运行时间将不会再坏了。 在应用中,这是一种最重要的需求, 通常, 除非特别指定, 我们提到的运行时间都是最坏情况的运行时间。

    而平均运行时间也就是从概率的角度看, 这个数字在每一个位置的可能性是相同的,所以平均的查找时间为n/2次后发现这个目标元素。平均运行时间是所有情况中最有意义的,因为它是期望的运行时间。也就是说,我们运行一段程序代码时,是希望看到平均运行时间的。可现实中,平均运行时间很难通过分析得到,一般都是通过运行一定数量的实验数据后估算出来的。一般在没有特殊说明的情况下,都是指最坏时间复杂度。

    六、算法空间复杂度

    我们在写代码时,完全可以用空间来换取时间,比如说,要判断某某年是不是闰年,你可能会花一点心思写了一个算法,而且由于是一个算法,也就意味着,每次给一个年份,都是要通过计算得到是否是闰年的结果。 还有另一个办法就是,事先建立一个有2050个元素的数组(年数略比现实多一点),然后把所有的年份按下标的数字对应,如果是闰年,此数组项的值就是1,如果不是值为0。这样,所谓的判断某一年是否是闰年,就变成了查找这个数组的某一项的值是多少的问题。此时,我们的运算是最小化了,但是硬盘上或者内存中需要存储这2050个0和1。这是通过一笔空间上的开销来换取计算时间的小技巧。到底哪一个好,其实要看你用在什么地方。

    算法的空间复杂度通过计算算法所需的存储空间实现,算法空间复杂度的计算公式记作:S(n)= O(f(n)),其中,n为问题的规模,f(n)为语句关于n所占存储空间的函数。

    一般情况下,一个程序在机器上执行时,除了需要存储程序本身的指令、常数、变量和输入数据外,还需要存储对数据操作的存储单元,若输入数据所占空间只取决于问题本身,和算法无关,这样只需要分析该算法在实现时所需的辅助单元即可。若算法执行时所需的辅助空间相对于输入数据量而言是个常数,则称此算法为原地工作,空间复杂度为0(1)。

    通常, 我们都使用"时间复杂度"来指运行时间的需求,使用"空间复杂度"指空间需求。当不用限定词地使用"复杂度'时,通常都是指时间复杂度。

    七、一些计算的规则

    1、加法规则

    T(n,m) = T1(n) + T2(m) = O(max{f(n), g(m)})

    2、乘法规则

    T(n,m) = T1(n) * T2(m) = O(max{f(n)*g(m)})

    3、一个经验

    复杂度与时间效率的关系:

    c(常数) < logn < n < n*logn < n^2 < n^3 < 2^n < 3^n < n!

    l------------------------------l--------------------------l--------------l

    较好                          一般                    较差

    八、常用算法的时间复杂度和空间复杂度

    43ae5571d7cd3370a015b3aa56277ad0.png

    --------------------------------------------

    参考:

    《大话数据结构》

    http://blog.csdn.net/yangwei282367751/article/details/52426911

    http://univasity.iteye.com/blog/1164707

    展开全文
  • Master 公式,可以直接确定形如上面时间消耗形式的时间复杂度: 如果 logb a ,复杂度:O(N^d) 如果 logb a > d,复杂度:O(N^(logb a)) 如果 logb a == d,复杂度:O(N^d * logN) 其中,logb a,指的是以b...
  • 1 如何评价、分析一个排序算法?很多语言、数据库都已经封装...分析一个排序算法,主要从以下3个方面入手:1.1 排序算法的执行效率1)最好情况、最坏情况和平均情况时间复杂度待排序数据的有序度对排序算法的执行效率...
  • 上一个排序随笔中分析了三种时间复杂度为O(n2)的排序算法,它们适合小规模数据的排序;这次我们试着分析时间复杂O(nlogn)的排序算法,它们比较适合大规模的数据排序。1 归并排序1.1 原理将待排序列划分前后两...
  • 快速排序快速排序的基本思想是:采取分而治之的思想,把大的拆分小的,每一趟排序,把比选定值小的数字放在它的左边,比它大的值放在右边;重复以上步骤,直到每个区间只有一个数。此时数组已经排序完成。快速排序...
  • 时间复杂度

    2021-03-05 23:23:14
    ArrayList部分一共五篇文章了,并且引入了时间复杂度来分析,强烈建议大家一定要按顺序阅读,相关文章分别是:最近看了一下评论区里,大家都急着想要了解HashMap,先不要着急,要完整的了解HashMap的内部实现,我们...
  • 这三种排序算法分别是桶排序、计数排序和基数排序,之所以它们的时间复杂度能到达O(n),是因为它们都是非基于比较的排序算法,不涉及元素之间的比较操作。1 桶排序1.1 原理将待排数据元素分配到几个有序的桶中,然后...
  • 时间复杂度为O(nlogn)的排序算法(归并排序、快速排序),比时间复杂度O(n²)的排序算法更适合大规模数据排序。归并排序归并排序的核心思想采用“分治思想”,将要排序的数组从中间分成前后两个部分,然后对前后两个...
  • //初始值-1,代表里面没有元素,使用时代表下标。 }*List; 第一种方法:顺序双指针法 指针i控制向后遍历,指针j记录需要交换的位置。、 1、进入循环,当遇到item元素时,不做任何处理,否则将指针i指向的值...
  • 一、复杂度理论、 二、时间复杂度、 1、P 与 NP 问题、 2、O 表示的复杂度情况、 3、时间复杂度取值规则、 4、时间复杂度对比、
  • 时间复杂度入门理解

    2021-01-14 05:56:19
    因此,对于模块化程序,优化其算法的时间复杂度是非常重要的。定义我们把一个算法中的语句执行次数定义频度,算法的运行时间刻画一个函数,定义 T(n) ,其中n称为问题的规模,当n不断变化时,T(n)也随之变化。...
  • 归并排序的时间复杂度为什么nlogn

    千次阅读 2021-02-17 23:00:49
    该递归树的高度log2n(计算过程:假设待排序的数组元素个数n,设高度x,x意味着n个元素需要连续二分x次才剩下1个元素,即n/2^x=1,x=log2n),每一层的总比较次数n,所以时间复杂度为nlogn。 快速排序的...
  • 认识时间复杂度为O(NlogN)的排序 剖析递归行为和递归行为时间复杂度的估算 用递归方法找一个数组中的最大值,系统上是怎么做的? 求中点的时候一般不使用(L+R)/2,防止溢出。 public class Code08_GetMax { public...
  • 算法的时间复杂度

    2021-10-17 17:29:02
    时间复杂度可直观理解代码执行时间的长短。实际上,由于受运行环境和输入规模的影响,代码的绝对执行时间是无法预估的,因此我们往往通过计算代码的基本操作执行次数来预估代码的执行时间。 以下面几种场景来说明...
  • 时间复杂度到底怎么算 算法(Algorithm)是指用来操作数据、解决程序问题的一组方法。对于同一个问题,使用不同的算法,也许最终得到的结果是一样的,但在过程中消耗的资源和时间却会有很大的区别。 那么我们应该...
  • 2、用T(n)表示程序执行次数3、用O(n)表示时间复杂度4、时间复杂度大小比较 写在前面 时间复杂度是用来干什么的? 时间复杂度可以用来衡量算法的执行效率。 1、数学中的log什么意思? 预备知识:数学中的log什么意思...
  • 展开全部 冒泡排序的基本思想是,对相邻的元素进行两两比较,顺序相反则进行交换,这样,每一趟会e68a8462616964757a686964616f31333433616161将最小或最大的元素“浮”到...综合来看,冒泡排序最好时间复杂度为是O(n).
  • 时间复杂度的计算

    2021-01-28 03:54:52
    1,算法复杂度是在《数据...一个是时间复杂度,一个是渐近时间复杂度。前者是某个算法的时间耗费,它是该算法所求解问题规模n的函数,而后者是指当问题规模趋向无穷大时,该算法时间复杂度的数量级。当我们评价一个...
  • 时间复杂度和空间复杂度算法效率时间复杂度大O渐进表示法(估算)空间复杂度 什么是数据结构? 数据结构(Data Structure)是计算机存储、组织数据的方式,指相互之间存在一种或多种特定关系的数据元素的集合。 什么是...
  • 其中,上面提到的效率可以用算法的时间复杂度来描述,而所占用的存储空间可以用算法的空间复杂度来描述。 时间复杂度:用于评估执行程序所消耗的时间,可以估算出程序对处理器的使用程度。 空间复杂度:用于评估...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 867,118
精华内容 346,847
关键字:

时间复杂度为0