精华内容
下载资源
问答
  • 链式存储中在第i个位置插入或删除时间复杂度
    万次阅读 多人点赞
    2016-12-05 21:12:05

    计算机的数据存储(物理结构)中有两种基本的方式:顺序存储链式存储。顺序存储指的是用一段地址连续的存储单元依次存储数据;而链式存储中数据元素可以散乱的存储到存储单元中,每一个数据元素中包含数据项和下一个元素的存储地址。

    通过二者的定义不难看出,顺序存储在查找时的时间复杂度为O(1),因为它的地址是连续的,只要知道首元素的地址,根据下标可以很快找到指定位置的元素,而对与插入和删除操作由于可能要在插入前或删除后对元素进行移动,所以顺序存储的时间复杂度为O(n)。链式存储的特性则正好相反,在查找时需要从头元素逐个寻找,因此查找的时间复杂度为O(n),而对于插入和删除操作,由于只需要变更数据元素中下一元素的存储地址即可,因此时间复杂度为O(1)

    表面上看上面的说法没有什么问题,但其实在日常的使用中,比如要在数据集合的第i个位置插入或删除一个元素,要完成这样一个动作,使用顺序存储需要查找到元素然后执行插入或删除,时间复杂度为O(1)+O(n)=O(n);而链式存储同样需要先查找到元素然后在插入或删除,时间复杂度为O(n)+O(1)=O(n)

    所以说链式存储插入和删除的时间复杂度为O(1)的前提应该是已知元素当前的位置,否则实现在第i个位置插入或删除一个元素,顺序存储和链式存储的时间复杂度是一样的,都是O(n).

    更多相关内容
  • 我的理解是它应该是O(N),然而,它给我一O(1).任何人都可以指出我在这里做错了什么?先谢谢你.public static void arrayListRemoveTiming(){long startTime, midPointTime, stopTime;// Spin the compute...

    我试图绘制ArrayList的remove(element)方法的Time Complexity.

    我的理解是它应该是O(N),然而,它给我一个O(1).任何人都可以指出我在这里做错了什么?

    先谢谢你.

    public static void arrayListRemoveTiming(){

    long startTime, midPointTime, stopTime;

    // Spin the computer until one second has gone by, this allows this

    // thread to stabilize;

    startTime = System.nanoTime();

    while (System.nanoTime() - startTime < 1000000000) {

    }

    long timesToLoop = 100000;

    int N;

    ArrayList list = new ArrayList();

    // Fill up the array with 0 to 10000

    for (N = 0; N < timesToLoop; N++)

    list.add(N);

    startTime = System.nanoTime();

    for (int i = 0; i < list.size() ; i++) {

    list.remove(i);

    midPointTime = System.nanoTime();

    // Run an Loop to capture other cost.

    for (int j = 0; j < timesToLoop; j++) {

    }

    stopTime = System.nanoTime();

    // Compute the time, subtract the cost of running the loop

    // from the cost of running the loop.

    double averageTime = ((midPointTime - startTime) - (stopTime - midPointTime))

    / timesToLoop;

    System.out.println(averageTime);

    }

    }

    展开全文
  • 时间复杂度:衡量算法流程中发生了多少次常数时间操作, 额外空间复杂度:衡量算法流程中必须开辟的空间。 1. LinkedList 基于链表实现。 /** * Inserts the specified element at the specified position in this...

    时间复杂度:衡量算法流程中发生了多少次常数时间操作,
    额外空间复杂度:衡量算法流程中必须开辟的空间。

    1. LinkedList

    基于链表实现。
    add:

    /**
         * Inserts the specified element at the specified position in this list.
         * Shifts the element currently at that position (if any) and any
         * subsequent elements to the right (adds one to their indices).
         *
         * @param index index at which the specified element is to be inserted
         * @param element element to be inserted
         * @throws IndexOutOfBoundsException {@inheritDoc}
         */
        public void add(int index, E element) {
            checkPositionIndex(index);
    
            if (index == size)
                linkLast(element);
            else
                linkBefore(element, node(index));
        }
    
    

    请注意这个node(index)的代码:

    /**
         * Returns the (non-null) Node at the specified element index.
         */
        Node<E> node(int index) {
            // assert isElementIndex(index);
    
            if (index < (size >> 1)) {
                Node<E> x = first;
                for (int i = 0; i < index; i++)
                    x = x.next;
                return x;
            } else {
                Node<E> x = last;
                for (int i = size - 1; i > index; i--)
                    x = x.prev;
                return x;
            }
        }
    

    这里进行了2分遍历查找相应坐标下的index节点!当插入坐标小于2分之size,从左边开始遍历,大于从右边开始遍历寻找节点,所以这部分的时间复杂度实为:O(N)
    当index == size时,说明在往集合的最后一个节点进行新增操作:

    
        /**
         * Links e as last element.
         */
        void linkLast(E e) {
            final Node<E> l = last;
            final Node<E> newNode = new Node<>(l, e, null);
            last = newNode;
            if (l == null)
                first = newNode;
            else
                l.next = newNode;
            size++;
            modCount++;
        }
    

    获得最后一个节点l,然后new Node<>(l, e, null),new了一个节点,指定该节点的上一个节点为l,值为e,即add的值,该节点的下一个节点此时为null。当创建完成后,最后一个节点指针指向新建的节点。再判断最后一个节点l是否为空。
    如果为空,说明此时集合为空,无值,头部指针再执行新建的节点,newNode作为集合内的第一个节点,头指针和尾指针都指向它。
    如果不为空,则l节点的next指向newNode,l作为newNode创建之前的尾节点。此是l和新的尾节点newNode的双端指向已构建完毕。
    节点创建完毕后,size++即长度++,而modCount记录的是此集合在结构上被修改的次数。 结构修改是那些改变列表大小的修改。
    可以发现节点插入的过程中只有指针指向发生了和长度计量发生了变化,所以add头部的时间复杂度为O(1),且并没有创建额外的集合空间,所以空间复杂度为O(1)。
    当index != size时,说明在往集合的中间或者最开始的部分进行新增:

        /**
         * Inserts element e before non-null Node succ.
         */
        void linkBefore(E e, Node<E> succ) {
            // assert succ != null;
            final Node<E> pred = succ.prev;
            final Node<E> newNode = new Node<>(pred, e, succ);
            succ.prev = newNode;
            if (pred == null)
                first = newNode;
            else
                pred.next = newNode;
            size++;
            modCount++;
        }
    
    

    succ是原集合中该下标对应的节点,现需要在该下标中插入一个新值。
    pred获取原节点的上一个节点,创建一个新的节点newNode,指定上一个节点为pred,传入值e,指定下一个节点为succ,同时指定succ的上一个节点为newNode。
    如果原节点的上一个节点为空说明,succ为头节点,而newNode即在头节点插入,first头部节点指针指向newNode。
    如果原节点的上一个节点不为空说明,succ为中间节点,同时让pred的next指针发生变化由succ变为newNode,此时双端节点构建完成。
    该过程的节点新增同样只有节点指针和长度发生了变化。但是,这部分需要找到相应index下标的Node节点,及上述调用的node(index)方法进行了遍历,所以时间复杂度为O(N),无额外空间,空间复杂度为O(1)。

    remove:

       public E remove(int index) {
            checkElementIndex(index);
            return unlink(node(index));
        }
       E unlink(Node<E> x) {
            // assert x != null;
            final E element = x.item;
            final Node<E> next = x.next;
            final Node<E> prev = x.prev;
    
            if (prev == null) {
                first = next;
            } else {
                prev.next = next;
                x.prev = null;
            }
    
            if (next == null) {
                last = prev;
            } else {
                next.prev = prev;
                x.next = null;
            }
    
            x.item = null;
            size--;
            modCount++;
            return element;
       }
    	
    

    remove的过程也无特殊变化,同样也是节点的指向变化而已。
    获取需要删除的下表对应的节点,获取该节点的上一个节点为prev,下一个节点为next。
    判断上一个节点prev是否为空,为空就说明它是头节点,不为空时,让删除节点的上一个节点prev的下一个节点指向删除节点的下一个节点next!同时让x需要删除的节点的上一个节点指针指向null。
    判断下一个节点next是否为空,为空就说明它是尾节点,不为空时,让删除节点的下一个节点next的上一个节点指向删除节点的上一个节点prev!即跳过x(需要删除的节点),同时让x的下一个节点指向null。
    让x的值变为null,长度–,修改次数++。
    删除节点x此时变为“孤儿”,没人指向它,它指向的是null。根据JDK1.8用的默认GC为 ParallelGC即PS + PO,其判断是否为垃圾的算法为根可达算法,即是否与内存有直接或间接的”链接“,由于x此时无指向,经过一次GC后判断其为“垃圾”,最终被回收掉了。
    可以发现reomve的过程同样也是指针的指向变化,无额外操作。但同样调用了遍历方法node(index)找到相应下标,此时的时间复杂度:O(N),空间复杂度O(1)。
    节点在集合的排列方式大致如下:
    在这里插入图片描述
    0为头节点,2为尾节点。之前有种说法是头节点的上一个节点指针指向尾节点,尾节点的下一个节点指针指向头节点。不过我这次在JDK1.8关于LinkedList的双端链表它的源码中并未发现这种结构。有兴趣可以交流下。正文继续。

    2. ArrayList

    基于数组实现。

       public void add(int index, E element) {
            rangeCheckForAdd(index);
    
            ensureCapacityInternal(size + 1);  // Increments modCount!!
            System.arraycopy(elementData, index, elementData, index + 1,
                             size - index);
            elementData[index] = element;
            size++;
        }
    

    ArrayList的新增操作的算法体现在 System.arraycopy(elementData, index, elementData, index + 1,size - index); elementData为它维护的一个Object[]数组。
    在Systen中,arraycopy是一个native方法即调用的是本地方法栈中的c语言编写的方法

        public static native void arraycopy(Object src,  int  srcPos,
                                            Object dest, int destPos,
                                            int length);
    

    src - 源数组。
    srcPos – 源数组中的起始位置。
    dest - 目标数组。
    destPos – 目标数据中的起始位置。
    length – 要复制的数组元素的数量。
    根据注释其实可以判断其作用,即将elementData数组从index的位置作为起始位置,size-index作为结束位置,插入到一个新的elementData数组的index+1的位置,从而覆盖这个新数组在index + 1位置后的数。index相当于空出来的一个位置,原值已经后移了一位,方法执行结束后再 elementData[index] = element;传值,完成指定下标的add操作。
    图解如下:
    在这里插入图片描述
    这里使用了两个数组进行操作,且截取了一个数组的起始位置和结束位置,这里根据数组的特性是使用了偏移量截取到了一个[index,index+1]范围数组,虽然看不到具体代码,但截取的数组必然要遍历插入到新数组,所以可以判断它的时间复杂度为O(N)。而空间复杂度,因为使用的仍是有限的空间,所以空间复杂度为O(1)。

     public E remove(int index) {
            rangeCheck(index);
    
            modCount++;
            E oldValue = elementData(index);
    
            int numMoved = size - index - 1;
            if (numMoved > 0)
                System.arraycopy(elementData, index+1, elementData, index,
                                 numMoved);
            elementData[--size] = null; // clear to let GC do its work
    
            return oldValue;
        }
    

    这里删除依然同理,需要删除的元素下标为index,截取了原数组范围为[index+1,size-1-index]范围的数组,即从需要删除的下标+1到最后一个坐标。然后遍历插入到数组,从index位置开始!根据数组的特性也就是说,原index位置的元素被index+1位置的元素覆盖掉了,后面的部分元素左移了一个位置,这样就实现了ArrayList的删除操作。与LinkedList不同的是:LinkedList利用GC回收掉节点。ArrayList覆盖元素。
    以此可以得出remove的时间复杂度为:O(N),空间复杂度为O(1)。

    3. 总结

    根据Index进行增加和删除时,LinkedList和ArrayList的时间复杂度和空间复杂度:

    时间复杂度空间复杂度
    LinkList尾部add为:O(1),其余情况都为:O(N)O(1)
    ArrayListO(N)O(1)

    4. 后言

    前途似海,来日方长。

    展开全文
  • 同时这也伴随着整个数组的数被删除后这数的元素会往前移动 并且数组的整体的长度会变小 */ struct SqlList{ int a[Max]={5,2,0,1,3,1,4}; int length=7; }; void del(SqlList &s,int x){ int k=0;//用来...

    #include <stdio.h>

    using namespace std;

    #define Max 50
    /*
    这个题表明要删除数组中值为某个数的所有元素
    同时这也伴随着整个数组的数被删除后这个数的元素会往前移动
    并且数组的整体的长度会变小 
    */

    struct SqlList{
        int a[Max]={5,2,0,1,3,1,4};
        int length=7;
    }; 

    void del(SqlList &s,int x){
        int k=0;//用来记录数组中值为x的数有几个决定我们往前移动多少 
        for(int i=0;i<s.length;i++){
            if(s.a[i]==x){
                k++;//找到和x向匹配的数进行记录到底有多少 
            }
            else{
                s.a[i-k]=s.a[i];//一开始k是为0的其实就是原来的数给原来的数 
            }
        }
        s.length=s.length-k;//这里的长度可以带出来 
    }

    int main(){
        SqlList s;
        printf("原来的数组为:\n");
        for(int i=0;i<s.length;i++){
            printf("%d  ",s.a[i]);
        }
        del(s,1);
        printf("现在的数组为:\n");
        for(int i=0;i<s.length;i++){//只是长度变化了,其实数组里面应该还有目前长度之外的数 
            printf("%d  ",s.a[i]);
        }
    }

    展开全文
  • 在长度为n的()上,删除第个元素,其算法的时间复杂度为O(n) A.只有表头指针的不带表头结点的循环单链表 B.只有表尾指针的不带表头结点的循环单链表 C.只有表尾指针的带表头结点的循环单链表 D.只有表头指针的带...
  • 如果我执行以下操作,则在python列表中交换元素时间复杂度是多少?案例1 :(惯用法)在列表中交换两个元素>>> a = [1, 2, 3, 4, 5]>>> a[1], a[3] = a[3], a[1] # Pythonic Swap --> x, y = y, ...
  • 优先队列和堆: 堆特别适合找k大、K小的特殊数据结构 翻转链表: 203 445 92 需要两指针,前指针和当前指针 nxt=cur.next cur.next=pre pre=cur cur=nxt 优先队列和堆: 堆特别适合找k大、K小的特殊数据结构...
  •    在之前的文章中的示例1和示例2中,我们通过观察可以发现,当在顺序存储结构的线性表中某个位置上插入或删除数据元素时,其时间主要耗费在移动元素上(换句话说,移动元素的操作为预估算法时间复杂度的基本...
  • 数据结构,在一双向链表中删除个元素时间复杂度怎么计算?
  • 问题描述:长度为n的顺序表L,编写一个时间复杂度为O(n),空间复杂度为O(1)的算法,该算法删除线性表中所有值为x的数据元素。 解决思想: 这个问题一个复杂的解决方法是依次遍历顺序表,遇到值为x的元素删除,...
  • 单链表插入删除元素时间复杂度探究

    万次阅读 多人点赞 2015-03-26 00:50:07
    单链表相比数组的优势在于插入删除元素快,不需要移动大量的元素,只需要改变指针的指向,那么插入删除操作的时间复杂度应该是O(1),但是这是不对的,应该分情况讨论。 单链表结构体声明: typedefstruct LNode { ...
  • 从链表中删除数据的时间复杂度真的是O(1)吗?

    千次阅读 多人点赞 2019-10-09 08:30:00
    本文经授权转载自微信公众号:小争哥(xiaozhengge0822),作者:小争哥数组和链表作为最基础的数据结构,在面试的时候,经常会被问到。最常被问到的一问题,那就是...
  • 给你一数组 nums 和一值 val,你需要 原地 移除所有数值等于 val 的元素,并返回移除后数组的新长度。 不要使用额外的数组空间,你必须仅使用 O(1) 额外空间并 原地 修改输入数组。 元素的顺序可以改变。你不...
  • 平时我们在计算单链表的第i个节点删除时间复杂度时一般认为是O(n),过程如下 1.先从头节点开始遍历链表,找到第i-1节点 2.将第i-1节点next指向第i个节点的next 可以看到时间主要花在了遍历链表上 如果我们...
  • 单链表插入删除操作的时间复杂度

    万次阅读 2019-11-10 10:31:23
    单链表相比数组的优势在于插入删除元素快,不需要移动大量的元素,只需要改变指针的指向,那么插入删除操作的时间复杂度应该是O(1),但是这是不对的,应该分情况讨论。 单链表结构体声明: typedefstruct LNode { ...
  • python3 list时间复杂度

    千次阅读 2020-12-24 01:17:26
    一、引题本周在做力扣上的算法题(删除排序数组中的重复项)时,遇到了超出时间限制的问题,后来才知道是我设计的算法时间复杂度过高,于是我就对list的各个基本操作和常用函数的复杂度作了了解。二、背景知识1.数组...
  • 引言我们在使用python开发过程中,list属于使用非常广泛的数据结构。不管是自己程序存放数据,还是处理接口...所以我们要剖析下list的各个方法的时间复杂度,以帮助我们在业务开发中对应该怎样用list或者是否该用lis...
  • 这里写自定义目录标题前言什么是跳表呢?跳表结构解释查找元素插入元素JAVA实现使用场景举例对整数排序和查找对自定义类型排序和...插入、删除元素后保持有序的时间复杂度为O(n) 因此链表一般是用在需要频繁插入或删除
  • 数组重复的问题在任何编程中都会有碰到了,这里介绍C语言删除无序整型数组中的重复元素时间复杂度,希望对各位有帮助。遇到一题,大概要求是写一函数处理来去掉一无序的整型数组(例如int i_arr[] = { 1, 2, ...
  • python_lintcode_372在O(1)时间复杂度删除链表节点_174删除链表中倒数n节点
  • 数组为何从0开始计数 ...因为数组具有以上两特性,计算机会给每内存单元分配一地址,通过地址来访问内存(数组)中的数据,当计算机随机访问某个数组元素时,会通过一寻址公式来进行查找:...
  • 堆排序怎么实现的 怎么插入新元素 时间复杂度
  • 给你一有序数组 nums ,请你 原地 删除重复出现的元素,使每个元素 只出现一次 ,返回删除后数组的新长度。 不要使用额外的数组空间,你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。 示例 1: ...
  • 基于此,初始时,将个元素看做是非重复的有序表,之后依次判断后面的元素是否与前面非重复有序表的最后一个元素相同,若相同则继续向后判断,不相同则插入到前面的非重复有序表的最后,直至判断结束为止。...
  • 链表的插入、删除、查找时间复杂度

    千次阅读 多人点赞 2020-07-25 13:44:08
    单向链表要删除某一节点...而若只知道待删除节点的序号,则依然要按序查找,时间复杂度仍为O(n)。 单、双链表的插入操作,若给定前驱节点,则时间复杂度均为O(1)。否则只能按序或按值查找前驱节点,时间复杂度为O(..
  • 问题描述:长度为n的线性表,删除表中所有值为x的元素,要求时间复杂度为O(n),空间复杂度为O(1)。 算法设计思想:用k记录顺序表中不等于x的元素个数,即需要保存的元素个数,边扫描L边统计k,并将不等于x的元素...
  • 如果我们要映射一值到布隆过滤器中,我们需要使用多不同的哈希函数生成多哈希值,并对每生成的哈希值指向的 bit 位置 1,例如针对值 “baidu” 和三不同的哈希函数分别生成了哈希值 1、4、7,则上图转变为...
  • 时间复杂度

    千次阅读 2021-03-27 18:23:39
    确定性算法的时间复杂度,一般有2维度:好坏情况,上下界 例如,找到数组中任意一小于0的数 时间复杂度 渐进下界Ω 渐进上界O 渐进确界θ 最好情况 ...
  • 一般大家都知道ArrayList和LinkedList的大致区别:1.ArrayList是实现了基于动态数组的数据结构,LinkedList基于链表的...3.对于新增和删除操作add和remove,LinedList比较占优势,因为ArrayList要移动数据。ArrayLis...
  • 列表list,一有序的队列列表内的个体为元素,由若干个元素按照顺序进行...以0开始查找方法:value,[start,[stop]]通过对应位置的索引进行查找,找到列表内的元素是否有匹配,如有则返回索引值匹配到个元素则立...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 108,563
精华内容 43,425
关键字:

删除第i个元素的时间复杂度

友情链接: 01.rar