精华内容
下载资源
问答
  • 顺序表和单链表的插入删除操作时间复杂度的区别 最近在学习数据结构,看到如果需要用到大量的插入和删除操作,单链表的效率会高于顺序表。看到这里时内有有个疑惑,这两种数据结构的插入和删除操作的时间复杂度不都...

    顺序表和单链表的插入删除操作时间复杂度的区别

    最近在学习数据结构,看到如果需要用到大量的插入和删除操作单链表的效率会高于顺序表。看到这里时内有有个疑惑,这两种数据结构的插入和删除操作的时间复杂度不都是O(n)吗?为什么会有这种说法呢?

    因此自己思考了下,结合计算机原理得出了一点自己的思考:

    单链表顺序表的插入删除操作的耗时因素主要差别于,数据元素的大小是不一定的,如果数据元素本身需要一块大内存,单链表里面费时的操作也就是指针后移,对指针类型这样一个小内存数据类型进行读取、CPU运算、和存储,而顺序表中费时的操作是对这种大内存数据元素的读取、CPU运算和存储,这明显比前者耗时更多。所以这两种存储结构线性表的插入操作虽然时间复杂度都是O(n),但这个n的单位时间是不同的,前者比较稳定且小,后者和数据元素大小有关。

    展开全文
  • 算法复杂度 3次循环就是 线性 线性表是一个有限序列,可以为空 线性表第一个元素没有直接前驱,最后一个元素没有直接后继 假设线性表有n个元素,如果在第i个位置插入一个新元素,需向后移动 n-i+1个元素 链式...

    https://www.bilibili.com/video/BV1xK4y1U7Dc 后(复杂度、顺序表、链表)笔记
    学数据结构,也就是算法并不单纯是应付考试,应付考试我不必写那么多,主要是做一个深刻的了解,平时多练练力扣的题  做不出来也要找出规律  https://leetcode-cn.com/ 
    (数据结构课本都是使用C语言作为示例)代码重构,提高后台响应速度,内存溢出,面试时我们会想到算法,工作中其实比较少使用,但不代表你不学,它类似木桶效应的短板。“ MySql 为什么索引要用 B+ 树”, 那什么是B+树,红黑树,你说不出一句话来,尽管它就是底层原理

    编译工具 : Microsoft Visual Studio

    课本的课后习题 也要看

    额,做不出来是其次,大部分情况是看不懂题意。。。哪位大佬可以指导一下
    总结一: 做题前要先画图  不容易错

    算法的设计要求包括,正确性、可读性、健壮性和效率与低储存量需求。
    (要改代码,尽量用接口,有问题时,不要用那个类,加个类进去)

    数据结构中,从逻辑上可以把数据结构分为 线性结构和非线性结构
    计算机算法指的是解决问题的有限步骤

    复杂度

    复杂度是用来分析程序和算法运行的时间和空间占用情况。
    时间复杂度 
    算法中的基本操作的执行次数,为算法的时间复杂度(时间复杂度不是计算程序运行多长时间,因为运行时间和设备上硬件有关。)

    计算时间复杂度 你可以运行一下C程序知道它的运算次数
    
    void fun(){
        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--){
            ++count;
        }
        print("%d\n",count);
    
    }
    F(N) = N^2 + 2*N+10
    大O的渐进表示法: 只需要大概执行次数 
    1、用常数1取代运行时间中的所有加法常数
    2、在修改后的运行次数函数中,只保留最高阶顶
    3、如果最高阶顶存在且不是1,则去除与这个项目相乘的常数,得到的就是大O阶
    这里使用大O的渐进表示法后, 时间复杂度为 O(N*N)  N平方

    O(1)不是只找一次  而是常数个
    二分查找时间复杂度O(log2n)  ,   
    最好的情况是O(1)  折半查找元素   一张纸对折   在大于中间值或小于中间值找,缩小一半的查找  
    计算过程:N/2/2/2../2 =1   N= 2^X   二的X次方  X是一张纸对折次数(查找次数)此时我们要的是X, 所以 x= log\binom{N}{2}

    long long Fib(size_t N){   
        return N<2 ? N : Fib(N-1)*Fib(N-2);
    }
    递归算法复杂度如何计算:  递归次数*每次递归函数的次数  斐波那契数列,下面画一个二叉树帮助理解
    
    1                 fib(n)
    
    2            fib(n-1)    fib(n-2)
    
    4    fib(n-2) fib(n-3)   fib(n-3)  fib(n-4)
    
    8 个fib   = 2^3
    
    答案是 2^0 + 2^1 + 2^2+...+2^(n-1) = 2^n  - 1     即O(2^N)
    测试一下Fib(100)到底要运行多久,会不会卡死,运行2的100次方 有30个0的数,我的计算机CPU目前是2.90GHz 也就是29亿次运行每秒,emem太大了等不了 运行Fib(50)吧
    
    
    递归计算斐波那契数列有非常多的重复 fib(n-1)返回fib(n-2) fib(n-3)。。,其中fib(n-2)重复计算了
    先定义数组,用空间换时间,时间复杂度为O(N)
    #include<stdio.h>
    #include<malloc.h>
    long long* Fib(size_t N){   
        long long* fibArray = malloc(sizeof(long long)*N);
        fibArray[0] = 0; //N是0直接返回0
        if(N==0)
            return fibArray;
        fibArray[1] = 1;
        for(int i=0; i <= N; ++i){
            fibArray[i] = fibArray[i-1] + fibArray[i-2]
        }
        return fibArray;
    }
    可以直接计算出 printf("%d\n",Fib(1000));

     斐波那契数列时间复杂度为O(2^N),空间复杂度是

    描述复杂度由低到高说明举例
    对数级别logN二分策略二分查找
    线性级别N循环找出最大元素
    线性对数级别NlogN归并排序
    指数级别2^N穷举查找检查所有子集

    2^N  和  N^2  大小问题:  2^0=1    0^2=0         2^10=1024    10^2=100       

     空间复杂度
    几乎不关注空间复杂度,摩尔定律:集成电路上可以容纳的晶体管数目在大约每经过18个月便会增加一倍,也就是内存每过1年半翻一倍;设备上的内存一直在变高。只有嵌入式很在意空间,设备大小手限制。
    时间复杂度不计算时间,计算大概运算次数。
    空间复杂度不计算空间(占用多少字节),计算大概定义的变量个数

    上面的Fib(){} ,开辟了N个空间, 空间复杂度是O(N)    
     

    算法复杂度  3次循环就是 N^{3}

    线性

    数组和链表是基础,要掌握 插入删除需要什么操作   比如说数组的移动位置链表的指针指向

    线性表

    线性表是N个具有相同特性的数据元素的有限序列。属于线性结构,也就是连续的一条直线,常见的线性表: 数组(顺序表),链表,栈,队列,字符串
    线性表是一个有限序列,可以为空 (空表)
    线性表第一个元素没有直接前驱,最后一个元素没有直接后继
    存储结构有顺序存储结构链式存储结构两种,前者称为顺序表,后者称为链表。存储结构就是物理结构,在内存中的数据的地址不一定是连续的。线性表只是在逻辑结构上是线性的。物理地址连续的存储单元是顺序表。

    假设线性表有n个元素,如果在第i个位置插入一个新元素,需向后移动(    ) 个元素
    程序中  end=n-1   n-1>=i时   后移  ps->a[end+1] = ps->a[end];
    需要后移的数量为 n-i+1
    
    
    设一个链表最常用的操作是在末尾插入节点和删除尾节点,则选用(D)最省时间。 
    某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素,则采用()存储方式最节省运算时间,选的答案是:带尾指针的单循环链表
     A、单链表 B、单循环链表 C、带尾指针的单循环链表 D、带头节点的双循环链表
    最省时间说明要避免遍历整个链表,链表末尾操作说明是循环链表,
    
    单链表无法得到前一个节点,删除尾节点和在链表末尾插入节点也要遍历全表
    带尾指针的单向链表:插入可以,但是删除无法完成,因为p需要前移,但是单向链表无法得到前一个节点。
    带尾指针的双向链表:插入和删除都很简单。
    带尾指针的单向循环链表:插入很简单,删除则需要遍历整个链表,比较费时。
    带头指针的双向循环链表:插入和删除都很简单。

    链表与顺序表区别

    • 链表

    优点: 插入和删除不需要移动其它元素,空间有效利用(扩容方便)
    缺点: 大量访问操作时不如顺序存储结构   不能随机访问

    • 顺序  

    优点: 1、可随机存取,存储密度高;       2、缓存利用率比较高
    缺点: 1、插入或删除操作时,需大量移动元素 时间复杂度O(N)               
      2、  要求连续的内存空间,空间不够时,增容会消耗内存(可能存在空间浪费,增容有一些效率损失)

    顺序表的缺点由链表解决了,链表和顺序表是互补的数据结构

    理解即可:

    什么叫随机访问?  像数组,直接访问第三个位置  第四个位置;而链表不行

    CPU计算时先看缓存中有没有,没有才到内存中找:(寄存器空间很小(几k)不可能直接存放一个数组)
    系统预加载,访问一个数据时,不会只加载一个数据到缓存,而是这个数据开始一段数据到缓存。
    数组的预加载很快,因为物理地址是连续的;

    顺序表

    物理地址连续的存储空间是顺序表。
     

    中间/头部插入删除,时间复杂度是O(N)

    .h文件是头文件,内含函数声明、宏定义、结构体定义等内容   .c文件是程序文件,内含函数实现,变量定义等内容,下面文件是 SeqList.h

    #pragma once
    
    //顺序表,有效数组在数组中必须是连续的  #define只能定义常量  这里用typedef定义int类型变量,以后返回类型你想改,这里改全局改
    //静态顺序表设计 --- 固定大小
    
    //常用的都是动态的顺序表  capicity空间不够则扩容
    //typedef  int SLDataType;
    //#define N 10
    //struct SeqList
    //{
    //    SLDataType* a; //指向动态开辟的数组  静态不传指针,使用这一条SLDataType a[N];
    //    int size;      //有效数据个数
    //    int capicity;  // 动态顺序表增加 容量空间的大小字段
    //};
    //可以用typedef定义  简写为SL
    typedef struct SeqList
    {
        SLDataType* a;  //指向动态开辟的数组
        size_t size;        //有效数据个数
        size_t capicity;    //容量空间的大小
    }SL, SeqList;
    //SeqList.c  
    #include "SeqList.h"
    
    //初始化
    //void slInit(SL* ps);//, size_t capicity
    //顺序表打印            
    //void slPrint(SL* ps);
    //尾插尾删  头插头删  中间插入删除
    //void slPushBack(SL* ps, SLDataType x);    //struct SeqList简写为SL
    //void slPopBack(SL* ps);    
    //void slPushFront(SL* ps, SLDataType x);   
    //void slPopFront(SL* ps);
    //在pos位置插入X  ,删除pos位置的值  
    //void SeqListInsert(SL* ps,int pos,SLDataType x);
    //void SeqListErase(SL* ps,int pos);
    //顺序表销毁            
    //void slDestory(SeqList* ps);
    //检查空间,如果满了,进行扩容 
    //void checkCapicity(SeqList* ps);
    //查找            
    //int slPrint(SL* ps, SLDataType x);
    
    //初始化
    void slInit(SL* ps){//, size_t capicity
        ps-> a= (SLDataType*)malloc(sizeof(SLDataType) *4);
        if(ps->a == NULL){
            printf("申请内存失败\n");
            exit(-1);
        }
        ps->size = 0;
        ps->capacity = 4;
    }
    
    //尾插
    void slPushBack()(SL* ps,SLDataType x){
        assert(ps); // 断言  ps指针不能为空
        checkCapicity(ps);
        ps->a[ps->size] = x;  //放到数组的 a[size]位置  size=3 a[3]越限
        ps->size++;
    }
    
    //打印
    void slPrint(SL* ps){
        assert(ps);
        for(int i=0;i< ps->size;++i){
            printf("%d", ps->a[i]);
        }
    }
    
    //尾删
    void slPopBack()(SL* ps, SLDataType x){
        assert(ps);
        //如果这里的a[ps->size-1]值是0  没报错??? 好吧 不删内存值,直接减数组长度,找回的时候,可以找回
        //ps->a[ps->size-1] = 0;
        ps->size--;
    }
    
    //头加
    void slPushFront()(SL* ps){
        assert(ps);
        checkCapicity(ps);
        int end = ps->size-1;
        while(end >= 0){//数组第0位也要移动
            ps->a[end-1] = ps->a[end]; //end的值挪到end+1的位置
            --end;
        }
        ps->a[0] = x;
        ps->size++;  
    }
    
    //头删
    void slPopFront(SL* ps){
        assert(ps);
        int start =0;
        while(start< ps->size-1){
            ps->a[start] = ps ->a[start+1];
            ++start;
        }
        ps->size--;
    }
    
    检查空间,如果满了,进行扩容 
    void checkCapicity(SeqList* ps){
        //如果满了需要扩容(如果原地有足够空间直接原地扩容,没有则另找一个新空间,把数组拷过去再释放掉旧的空间)
        if(ps->size >= ps->capacity){
            //通常增2倍
            ps->capacity *=2;
            ps->a = (SLDataType*)realloc(ps->a, sizeof(SLDataType)*ps->capacity);
            if(pa->a == NULL){
                  printf("扩容失败\n");
                  exit(-1);   
            }   
        }
    }
    
    void slDestory(SL* ps){
        free(ps->a); //空间释放
        ps->a = NULL; //指针设置为空 防止野指针
        ps->size = ps->capacity =0;
    }
    
    
    //在pos位置插入X (插入位置往后全部挪一位) ,删除pos位置的值(往前挪一位)  
    void SLInsert(SL* ps,int pos,SLDataType x){
        assert(ps);
        assert(pos < ps->size && pos >=0); //断言为真就没事 
        checkCapicity(ps);
        int end = ps->size-1;
        while(end >= pos){
            ps->a[end+1] = ps->a[end];
            --end;
        }
        ps->a[pos] = x;
        ps->size++;
    }
    void SLErase(SL* ps,int pos){
        assert(ps);
        assert(pos <= ps->size && pos >=0);
    
        int start= pos;      
        while(start< ps->size-1){
            ps->a[start] = ps ->a[start+1];
            ++start;
        }
        ps->size--; 
    
    }
    
    
    
    //查找下标            
    int slPrint(SL* ps, SLDataType x){
        assert(ps);
        int i=0;
        while(i< ps->size){
            if(ps->a[i] == x){
                return i;
            }
        }
        return -1;
    }

    free(ps) 释放的是指针还是内存?释放的是指针指向的内存
    内存泄露 是指针丢了还是内存丢了?  指针丢了

    //test.c
    #include "SeqList.h"
    
    //测试头尾插入删除
    void TestSeqList1(){
        SeqList s;
        slPushBack(&s,1);
        slPushBack(&s,2);
        slPushBack(&s,3);
        slPushBack(&s,4);
        slPrint(&s);
        slPopBack(&s);
        slPopBack(&s);
        slPrint(&s);
    
        slPushFront(&s,-1);
        slPushFront(&s,-2);
        slPrint(&s);
    }

    算法题  移除元素  数组删除指定元素

    如果按照正常的解法,那么数组 3  1  6  3  5  3  7循环
    one: 正常的解法 时间复杂度O(N^2)  空间复杂度O(1)
    for(int i=0;i<a->size;i++){
        if(a[i]==3){
            //后面的数字往前挪
            for(int start=i; start<a->size-1; ++start){
                ps->a[start] = ps ->a[start+1];
            }
            a->size--;
        }
    }
    
    
    two: 不考虑空间复杂度,直接复制一个数组
    做法: 定义一个新数组,遍历原数组,发现不是3就给添加到新数组里面;遍历完成后吧新数组复制到原数组,新数组删掉,返回数组长度
    
    突然发现题干要求的是返回数组长度不是输出删除元素后的数组,,,所以我们现在可以不定义新数组,直接遍历原数组,发现不是3就计数+1
    for(int i=0;i<a->size;i++){
        if(a[i]==3){
            ++count;
        }
    }
    
    three : 前面的做法依然不符合时间复杂度O(N) 使用双指针
    
        public int removeElement(int[] nums, int val) {
            if (nums == null || nums.length == 0)
                return 0;
            int i = 0,j =0;
            int length= nums.length;
            while(i<length){
                if(nums[i] != val){
                    nums[j] = nums[i];
                    j++;
                }
                i++;
            }
                return j;
        }
    

    双指针方法解可以解决时间复杂度问题

    链表

    非连续的物理存储结构;   链表每个元素用指针连接;  现实中最常用,针对顺序表缺点设计的

    一些题只要你会就掌握了

    1、反向输出带头节点的单链表全部节点的值。
    2、找出带头节点的单链表倒数第K个节点。
    3、判断单链表是否有环
    4、找出两个汇聚单链表的公共节点在这里插入图片描述

    https://blog.csdn.net/qq_41740162/article/details/105349989

    1、时间复杂度O(N)  递归
    void printList(ListNode *pp){
        if(pp == NULL) return;
        printList(pp->next);
        printf("%d",pp->data);
        return;
    }
    2、找出倒数节点    先将p1向右移动k次,只需要继续保持p1和p2等间距的右移,当p1的next为null,则证明p2所指的结点的值为倒数第k个节点的值
    ListNode *FindKNode(LinkList ll,unsigned int k){
        ListNode *pp1 = LL->next;
        ListNode *pp2 = LL->next;
        int i=0;
        //先定位到K个节点
        while((pp1!=NULL) && (i<k)){
            pp1 = pp1->next;
            i++;
        }
        if(ppl==Null) return NULL;
        while(1){
            //pp1继续直到null  此时的pp2就是倒数几个
            ppl = ppl->next;
            if(ppl==Null) break;
            pp2 = pp2->next;
    
        }
        return pp2;    
    }
    3、“快慢指针”的方法。就是有两个指针fast和slow,开始的时候两个指针都指向链表头head,然后在每一步
    操作中slow向前走一步即:slow = slow->next,而fast每一步向前两步即:fast = fast->next->next。
    两者之间的距离逐渐缩小:...、5、4、3、2、1、0 -> 相遇。又因为在同一个环中fast和slow之间的距离不会大于换的长度,因此到二者相遇的时候slow一定还没有走完一周(或者正好走完以后,这种情况出现在开始的时候fast和slow都在环的入口处)
    typedef struct node{ 
        char data ; 
        node * next ; 
    }Node; 
    bool exitLoop(Node *head) 
    { 
        Node *fast, *slow ; 
        slow = fast = head ; 
       
        while (slow != NULL && fast -> next != NULL) 
        { 
            slow = slow -> next ; 
            fast = fast -> next -> next ; 
            if (slow == fast) 
                return true ; 
        } 
        return false ; 
    } 

    单链表    

    链表在物理上是上一个节点存下一个节点的地址
    节点next 用于指向下一个节点的指针   链表的最后存的是0X0000 0000

    大部分的题都是带头单链表为主(双向链表不好出题   -_-!),但在实际开发中是双向链表为主

    SList.h        

    #pragma once
    #include<stdio.h>
    
    
    //节点
    typedef struct SListNode
    {
        SListDataType* data;  //
        struct SListNode* next;
    }SLTNode;
    
    
    void SListPopBack(SListNode** phead);
    void SListPushBack(SListNode** phead,SListDataType x);
    void SListPushFront(SListNode** phead,SListDataType x);
    void SListPopFront(SListNode** phead);
    void SListSize(SListNode* phead);
    void SListPrint(SListNode* phead)

    SList.c

    #pragma once
    #include "SList.h"
    #include<stdio.h>
    #include<stdlib.h>
    
    
    void SListPrint(SListNode* phead){
        SListNode* cur = phead;
        while(cur!=NULL){
            printf("%d",cur->data);
            cur = cur->next;           //重点: 下一个节点地址付给当前节点
        }
    }
    
    
    void SListSize(SListNode* phead){
    
    }
    
    
    //链表尾部插入
    //SListNode* phead是指针,我传指针给你,你对指针进行赋值,返回该指针,会不会影响外边的指针? 不会,应该传地址 也就是二级指针  而只读的传指针*就够了
    void SListPushBack(SListNode** pphead,SListDataType x){
        SListNode* newNode = BuySListNode(x);
        if(*pphead == NULL){
            *pphead = newNode;
        }else{
            //找到尾部的地址  尾部节点地址->next为NULL
            SListNode* tail = *pphead;
            while(tail->next!=NULL){
                tail = tail->next;           //重点: 下一个节点地址付给当前节点
            }
            tail->next = newNode;
        }  
    }
    
    
    SListNode* BuySListNode(SListDataType x){
        SListNode* newNode = (SListNode*)malloc(sizeof(SListNode));
            if(newNode == NULL){
                printf("申请节点失败\n");
                exit(-1);
            }
            newNode->data = x;
            newNode->next = NULL;
            return newNode;
    }
    
    //链表尾部删除
    void SListPopBack(SListNode** pphead){
        //空
        //一个节点
        //一个节点以上
        if(*pphead == NULL){
            return;
        }
        else if((*pphead)->next == NULL){
            free(*pphead);  //就一个节点  删了就没了
            *pphead = NULL;
        }else{
            SListNode* prev = NULL; //倒数第二个链表的地址
            SListNode* tail = *pphead;
            while(tail->next!=NULL){
                prev = tail;
                tail = tail->next;
            }
            free(tail);
            prev->next = NULL;
        }
    }
    
    //头插  
    void SListPushFront(SListNode** phead,SListDataType x){
        SListNode* newNode = BuySListNode(x);
        newNode->next = *phead;
        *pphead = newNode;
    }
    //头删
    void SListPopFront(SListNode** phead){
        //空
        //一个节点和一个节点以上
        if(*pphead == NULL){
            return;
        }
        else{
            SListNode* next = (*pphead)->next; 
            free(*pphead); 
            
            *pphead= next;
        }
    }
    
    
    //单链表查找
    SListNode* SListFind(SListNode* phead,SListDataType x){
        SListNode* cur = phead;
        while(cur){
            if(cur->data == x){
                return cur;
            }
            cur = cur->next;
        }
        return NULL;
    }
    //给出insert值查找
    SListNode* SListFind(SListNode* phead,unsigned int index){
        if(phead == NULL){
            return;
        }
        int i=0; //指向第几个节点
        SListNode* cur = phead;
        while(cur!=NULL && (i < index)){
            cur = cur->next; i++;
        }
        if(!cur){ return NULL; }//超出了表长
        return cur;
    }
    
    //中间插探讨 为什么是后面插,因为单链表你要前面插需要找到它前面是谁,我们单链表只记录后面一个节点的指针
    // newnode新生成的要插入的节点  pos 新生成的的节点之前的节点
    pos->next = newnode;
    newnode->next = pos->next;
    //因为  pos->next = newnode; 导致下一行的原本pos->next的值是空  必须先保存原本pos->next的值 s所以我们把两个式子颠倒即可
    newnode->next = pos->next;
    pos->next = newnode;
    
    void SListInsetAfter(SListNode* pos,SListDataType x){
        assert(pos);
        SListNode* newNode = BuySListNode(x);
        newNode->next = pos->next;;
        pos->next = newNode;
    }
    
    //删除
    void SListInsetAfter(SListNode* pos,SListDataType x){
        assert(pos);
        if(pos->next){
            SListNode* next = pos->next;
            SListNode* nextnext = next->next;
            pos->next = nextnext;
            free(next);
        }
    }
    //test.c
    #include "SList.h"
    
    //测试头尾插入删除
    int main(){
        SListNode* pList = NULL;
    
    
        SListPushBack(&pList,1);//SListPushBack(pList,1); 形参改成SListNode**了,应该传指针的地址
        SListPushBack(&pList,2);
        SListPushBack(&pList,3);
        SListPushBack(&pList,4);
        SListPrint(pList);
    
        SListPopBack(&pList);
        SListPopBack(&pList);
        SListPrint(pList);
        return 0;
    }

    反转链表(力扣)    经常遇到

     

    解题思路:
    假设n2 当前指针指向1,然后n1就是n2的前一个节点,指针为NULL,n3为当前指针的下一个指针
    当n2不为NULL时,进行循环。
    
          n1  n2   n3            
        null   1 ->2 -> 3 -> 4 -> 5 -> null
        
              n1  n2    n3            
        null   1 ->2 -> 3 -> 4 -> 5 -> null
        
                  n1   n2    n3            
        null   1 ->2 -> 3 -> 4 -> 5 -> null
        
                       n1   n2    n3            
        null   1 ->2 -> 3 -> 4 -> 5 -> null
        
                            n1   n2     n3            
        null   1 ->2 -> 3 -> 4 -> 5 -> null
                                  n1    n2      n3            
        null   1 ->2 -> 3 -> 4 -> 5 -> null     结束
    
    
    第二种思路: 原地反转链表
    原数组头节点直接指向空 5先插进去  然后插4  按要求插的个数结束后,其它为插入的数据直接全部头插
    翻转前   头节点head->1 ->2 -> 3 -> 4 -> 5 -> null
    翻转   头节点head-> null
    翻转     头节点head->5 -> null
    翻转     头节点head->5 -> 4 -> null
    翻转后   头节点head->5 -> 4 ->  3 -> 2 ->1 -> null

    /**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     struct ListNode *next;
     * };
     */
    
    
    struct ListNode* reverseList(struct ListNode* head){
        if(head==NULL || head->next == NULL){
            return head;
        }
        struct ListNode* n1 = NULL, *n2=head, *n3= head->next;
        while(n2){
            //反转
            n2->next = n1;
            //迭代
            n1 = n2;
            n2 = n3;
            if(n3)
                n3 = n3->next;
        }
        return n1;
    }
    
    //上面是视频的老师的写法,本人想不到用struct ListNode* n1 = NULL, *n2=head, *n3= head->next;定义。。。写成这种
        ListNode* n1 = NULL; 
        ListNode* n2=head; 
        while(n2){
            ListNode* n3= head->next;
            //反转
            n2->next = n1;
            //迭代
            n1 = n2;
            n2 = n3;
            if(n3)
                n3 = n3->next;
        }
    
    
    第二种思路: 原地反转链表
    struct ListNode* reverseList(struct ListNode* head){
        if(head==NULL || head->next == NULL){
            return head;
        }
        ListNode* ss = head->next,
        ListNode* ssnext;
        while(ss){
            //保留ss下一个节点的地址
            ssnext = ss->next;
            //迭代  在head后插入ss节点
            ss->next = head->next;
            head->next = ss;
            ss= ssnext;
        }
        return ss;
    }

    双向链表

    每一个节点包含两个指针,一个指向前节点prev,  一个指向next节点
    链表一个节点都没有(链表为空)时, head  next  prev  都指向自己。

    下图是带头双向循环链表   特点:结构复杂,操作简单            

    有空再画图吧

     尾插   假设有phead的指针   它有一个指向尾部的指针,不用找尾

     ( 我为什么把链表的名字定义成phead   ; 链表首地址就是head ;   path=head   head头)

    #pragma once
    #include<stdio.h>
    #include<assert.h>
    #include<stdlib.h>
    typedef int LTDataType;
    
    typedef struct ListNode
    {
        LTDataType data;  //
        struct ListNode* next;
        struct ListNode* prev;
    };
    //尾插
    void ListPushBack(ListNode* phead, LTDataType x){
        assert(phead);
        //双向链表最容易找到尾
        ListNode* tail = phead->prev; 
        ListNode* newnode = BuyListNode(x);
        // phead  ...  tail newnode
        tail->next = newnode;
        newnode->prev = tail;
        newnode->next = phead; 
        phead->prev = newnode;
    }
    // 头插与尾插类似  简单   phead newnode first 
    ListNode* first = phead->next;    ListNode* newnode = BuyListNode(x);
    newnode->next = first;  
    newnode->prev = phead; //这一句我差点写成 phead->prev
    phead->next = newnode;  // 不是插到头节点左边,而是头节点右边
    first->prev = newnode;
    //头删 就是删掉first   phead first second
    ListNode* first = phead->next;    ListNode* second = first->next;
    phead->next = second;
    second->prev = phead;
    free(first)
    
        
    void ListPopBack(ListNode* phead){
        assert(phead);
        ListNode* tail = phead->prev;
        //phead  .. tail->prev tail
        ListNode* prev = tail ->prev;
        prev->next = phead;
        phead->prev = prev;  
        free(tail);
        tail = NULL;
    }
    
    void ListInit(){ //ListNode** pphead
        /*(*pphead) = BuyListNode(0);
        (*pphead)->next = *pphead;
        (*pphead)->prev = *pphead;*/
        ListNode* phead = BuyListNode(0);
        phead->next = phead;
        phead->prev = phead;
    }
    
    ListNode* BuyListNode(SListDataType x){
        ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
            newNode->data = x;
            newNode->next = NULL;
            newNode->prev = NULL;
            return newNode;
    }
    
    void ListPrint(ListNode* phead){
        assert(phead);
        //循环链表永远不会空,看头节点
        ListNode* cur = phead->next;
        while(cur != phead){
            printf("%d\t", cur->data);
            cur = cur->next;
        }
    }
    
    ListNode* ListFind(ListNode* phead,LTDataType x){
        assert(phead);
        ListNode* cur = phead->next;
        while(cur!=phead){
            if(cur_data == x){
                return cur;
            }
            cur = cur->next;
        } 
        return NULL;
    }
    
    //在pos前面插x  
    // posPrev newnode pos  注意插入位置  pos前面 
    void ListInsert(ListNode* pos,LTDataType x){
        assert(pos);
        ListNode* posPrev = pos->prev;
        ListNode* newnode = BuyListNode(x);
        pos->prev = newnode;
        newcode->next = pos;
        newcode->prev = proPrev;
        posPrev->next = newnode;
    }
    
    void ListErase(ListNode* pos){
        assert(pos);
        assert(pos!=phead);
        ListNode* posPrev = pos->prev;
        ListNode* posNext = pos->next;
        posPrev->next = posNext;
        posNext->prev = posPrev;
        free(pos);
    }
    
    
    //清空数据
    void ListClear(ListNode* pphead){
        assert(pos);
        //清理所有数据节点,保留头节点,可继续使用
        ListNode* cur = phead;
        while(cur!= phead){
            ListNode* next = cur->next;
            free(cur);
            cur = next;
        }
        phead->next = phead;
        phead->prev = phead;
    }
    void ListDestory(ListNode** phead){ //因为要修改原值,必须传指针的地址
        assert(*pphead);
        ListClear(*pphead);
        free(*pphead);
        //经常忘记把指针设置为空  差点变成野指针了
        *pphead = NULL;//phead = NULL;的话这里指针销毁了,但外面实参的指针还在
    }
    //test.c
    #include "SList.h"
    
    //测试头尾插入删除
    int main(){
        ListNode* phead = ListInit();//&phead
    
        ListPushBack(phead ,1);//SListPushBack(pList,1); 形参改成SListNode**了,应该传指针的地址
        ListPushBack(phead ,2);
        ListPushBack(phead ,3);
        ListPushBack(phead ,4);
        ListPrint(phead );
    
        ListPopBack(phead);
        ListPopBack(phead);
        ListPrint(phead);
        return 0;
    }

    循环链表

     循环链表,特点是表中最后一个节点不再是空,而是指向头节点。
    可以是单链表也可以是双向链表

    循环单链表基本操作类似于单链表,单链表中最后一个节点的条件是 
    if(p!=NULL) 或 if(p->next!=NULL)
    循环链表的是 下一个节点是否是头节点
    if(p!=head) 或 if(p->next!=head)

    考点:

    顺序表合并

    (两个升序顺序表合并成一个升序顺序表)归并排序

    LA  1  7  8
    LB  3  4  9  10
    LC
    
    1 -- 3  1比较小    LC 1
    7 -- 3  3小        LC 1 3
    7 -- 4  4小        LC 1 3 4
    7 -- 9  7小        LC 1 3 4 7
    8 -- 9  8小        LC 1 3 4 7 8
    只剩下LB  合并到LC  具体实现类似力扣 88. 合并两个有序数组 区别是
    
    
    void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n){
        //上次: 先拷贝M数组二数据到数组一N,在对数组一进行排序  MN为数组的长度
        // 此时时间复杂度为 O( (M+N)* log(M+N))    log以2为底简写成log
        // 怎么优化到 O(M+N)
        //   nums1 = [1,2,3,0,0,0]
        //   nums2 = [2,5,6]
        //  num1[0] 比 num2[0]  num1[0] 比较小,把num1值加到新数组
        //  num1[1] 比 num2[0]  相等,把num1都加到新数组
        //  num1[2] 比 num2[0]  num2[0] 比较小,把num2值加到新数组   此时M也就是数组一种存在的数已经和数组二的第一个元素对比完了,新数组为[1,2,2]
    
        //  num1[2] 比 num2[1]  num1[2] 比较小,把num1值加到新数组
        // num1[3]超出范围不比较  剩下num2[1] num2[2]没比较的比较一下复制到新数组
    
    
        //  申请空间
        int* tmp = (int*)malloc(sizeof(int)*(m+n));
        int i1 =0,i2=0;
        int index =0;
        while( i1<m && i2<n ){
            if(nums1[i1] < nums2[i2]){
                tmp[index] = nums1[i1];
                ++index;
                ++i1;
            }else{
                tmp[index] = nums2[i2];
                ++index;
                ++i2;
            }
        }
    
        while(i1 < m){
            tmp[index] = nums1[i1];
            ++index;
            ++i1; 
        }
        while(i2 < n){
            tmp[index] = nums2[i2];
            ++index;
            ++i2; 
        }
    
        memcpy(nums1,tmp,sizeof(int)*(m+n));
        free(tmp);
    
    }

    第十五题  合并两个升序单链表

    public ListNode Merge(ListNode list1,ListNode list2) {
            if(list1 == null){
                return list2;
            }
            if(list2 == null){
                return list1;
            }
            ListNode head = null;  //头结点
            ListNode cur = null;  //当前连接节点
            //遍历两个链表
            while(list1 != null && list2 != null){
                if(list1.val <= list2.val){//取LA LB中较小者
                    if(head == null){
                        //第一次连接新链表
                        head = cur = list1;
                    }else{
                        //连接新链表
                        cur.next = list1;
                        //移动连接指针
                        cur = cur.next;
                    }
                    list1 = list1.next;
                }else{
                    if(head == null){
                        //第一次连接新链表
                        head = cur = list2;
                    }else{
                        //连接新链表
                        cur.next = list2;
                        //移动连接指针
                        cur = cur.next;
                    }
                    list2 = list2.next;
                }
            }
            //两个链表其中有一个遍历结束
            if(list1 == null){
                cur.next = list2;
            }
            if(list2 == null){
                cur.next = list1;
            }
            //返回新链表头
            return head;
        }

    合并两个循环链表, 一个在前一个在后

    已知a[0][0] 为123; a[2][2]则为?
    顺序表是连续的, 第三行第三列可以直接推出来哦       2m+2=10   答案是133
    
    123-》
     00    01    02    03    
     10    11    12    13
     20    21    22    23
     30    31    32    33
    
    a[3][3] == 123+ 3m+3 = 138 

    顺序结构(数组)可以存储非线性的,但浪费空间。
    已知一个顺序线性,设每个节点需占m个单元,若第0个元素的地址为addr,则第i个节点的地址为 addr+m*i

    展开全文
  • 算法时间复杂度

    2021-05-24 10:13:49
    算法的时间复杂度是衡量一个算法效率的基本方法。在阅读其他算法教程书的时候,对于算法的时间复杂度的讲解不免有些生涩,难以理解。进而无法在实际应用中很好的对算法进行衡量。《大话数据结构》一书在一开始也针对...

    算法的时间复杂度是衡量一个算法效率的基本方法。在阅读其他算法教程书的时候,对于算法的时间复杂度的讲解不免有些生涩,难以理解。进而无法在实际应用中很好的对算法进行衡量。《大话数据结构》一书在一开始也针对算法的时间复杂度进行了说明。这里的讲解就非常明确,言简意赅,很容易理解。下面通过《大话数据结构》阅读笔记的方式,通过原因该书的一些简单的例子和说明来解释一下算法的时间复杂度和它的计算方法。

    首先从基本定义下手,来了解一下什么是“算法的时间复杂度”,《大话数据结构》一书中对算法的时间复杂度定义如下:“算法语句总的执行次数 T(n) 是关于问题规模 n 的函数,进而分析 T(n) 随 n 的变化情况并确定 T(n) 的数量级。算法的时间复杂度,也就是算法的时间度量,记作:T(n) = O(f(n)) 它表示随问题规模 n 的增大,算法执行时间的增长率和f(n) 的增长率相同,称作算法的渐进时间复杂度,简称为时间复杂度。其中 f(n) 是问题规模 n 的某个函数。”光从定义来理解算法的时间复杂度还是比较难的,我们再结合一个简单的例子来说明。计算 1 + 2 + 3 + 4 + ......  + 100 = ? 这样的问题想必大家都遇到过,这里我们通过 C 语言用最简单的方法实现一下这个问题的算法。、

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

    for (int i = 1; i <= n; i++) {        //执行了 n + 1 次

    sum += i;        //执行了 n 次

    }

    printf(" sum = %d", sum);        //执行了 1 次

    从代码附加的注释可以看到所有代码都执行了多少次。那么这写代码语句执行次数的总和就可以理解为是该算法计算出结果所需要的时间。所以说,上述结算 1 + 2 + 3 + 4 + ......  + 100 = ?的算法所用的时间(算法语句执行的总次数)为 :1 + ( n + 1 ) + n + 1 = 2n + 3

    而当 n 不断增大,比如我们这次所要计算的不是 1 + 2 + 3 + 4 + ......  + 100 = ? 而是 1 + 2 + 3 + 4 + ......  + n = ?其中 n 是一个十分大的数字,那么由此可见,上述算法的执行总次数(所需时间)会随着 n 的增大而增加,但是在 for 循环以外的语句并不受 n  的规模影响(永远都只执行一次)。所以我们可以将上述算法的执行总次数简单的记做:2n 或者简记  n这样我们就得到了我们设计的计算 1 + 2 + 3 + 4 + ......  + 100 = ?的算法的时间复杂度,我们把它记作:O(n)

    对于同一个问题,解法通常是不唯一的。比如 1 + 2 + 3 + 4 + ......  + 100 = ?这个问题,还有其他的不少算法。我们再来看一个数学家高斯解决这个问题的算法。SUM = 1 + 2 + 3 + 4 + ......  + 100

    SUM = 100 + 99 + 98 + 97 + ...... + 1

    SUM + SUM = 2*SUM = 101 + 101 + 101 + .... + 101          正好 100 个 101

    SUM =  (100*101)/2 = 5050

    同样我们将这个解法翻译成 C 语言代码:

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

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

    printf("sum = %d", sum);        //执行 1 次

    这样我们针对同一个 1 + 2 + 3 + 4 + ......  + 100 = ?问题,不同的算法又的到了一个算法的时间复杂度:O(3)    一般记作 O(1) 我们后续给出原因。

    从感官上我们就不难看出,从算法的效率上看,O(3) < O(n) 的,所以高斯的算法更快,更优秀(是最优秀的吗?)。这种用个大写的 O 来代表算法的时间复杂度的记法有个专业的名字叫“大O阶”记法。那么通过对上述的例子进行总结,我们给出算法的时间复杂度(大O阶)的计算方法。

    推导“大O阶”的步骤:

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

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

    3、如果最高阶项存在且不是 1 ,则去除与这个项相乘的常数。

    下面我们在通过一个有不少 for 循环的例子按照上面给出的推导“大O阶”的方法来计算一下算法的时间复杂度。先看一下下面的这个例子的代码,也是用 C 语言写的,在注释上我们仍然对执行次数进行说明。

    int n = 100000;        //执行了 1 次

    for (int i = 0; i < n; i++) {        //执行了 n + 1 次for (int j = 0; j < n; j++) {        //执行了 n*(n+1) 次printf("i = %d, j = %d\n", i, j);        //执行了 n*n 次

    }

    }

    for (int i = 0; i < n; i++) {        //执行了 n + 1 次

    printf("i = %d", i);        //执行了 n 次

    }

    printf("Done");        //执行了 1 次

    上面的代码严格的说不能称之为一个算法,毕竟它很“无聊而且莫名其妙”(毕竟算法是为了解决问题而设计的嘛),先不论这个“算法”能解决什么问题,我们看一下它的“大O阶”如何推导,还是先计算一下它的执行总次数:

    执行总次数 = 1 + (n + 1) + n*(n + 1) + n*n + (n + 1) + 1 = 2n^2 + 3n + 3    这里 n^2 表示 n 的 2次方。

    按照上面推导“大O阶”的步骤我们先来第一步:“用常数 1 取代运行时间中的所有加法常数”,则上面的算式变为:执行总次数 = 2n^2 + 3n + 1    这里 n^2 表示 n 的2次方

    第二步:“在修改后的运行次数函数中,只保留最高阶项”。这里的最高阶是 n 的二次方,所以算式变为:执行总次数 = 2n^2    这里 n^2 表示 n 的2次方

    第三步:“如果最高阶项存在且不是 1 ,则去除与这个项相乘的常数”。这里 n 的二次方不是 1 所以要去除这个项的相乘常数,算式变为:执行总次数 = n^2    这里 n^2 表示 n 的2次方

    因此最后我们得到上面那段代码的算法时间复杂度表示为: O( n^2 )        这里 n^2 表示 n 的2次方。至此,我们对什么是“算法的时间复杂度”和“算法的时间复杂度”表示法“大O阶”的推导方法进行了简单的说明。当然要想在日后的实际工作中快速准确的推导出各种算法的“大O阶”我们还需要进行大量的联系,毕竟熟能生巧嘛。最后我们在把常见的算法时间复杂度以及他们在效率上的高低顺序记录在这里,是大家对算法的效率有个直观的认识。

    O(1) 常数阶 < O(logn) 对数阶 < O(n) 线性阶 < O(nlogn) < O(n^2) 平方阶 < O(n^3) < { O(2^n) < O(n!) < O(n^n) }

    最后三项我用大括号把他们括起来是想要告诉大家。如果日后大家设计的算法推导出的“大O阶”是大括号中的这几位,那么趁早放弃这个算法,在去研究新的算法出来吧。因为大括号中的这几位即便是在 n 的规模比较小的情况下仍然要耗费大量的时间,算法的时间复杂度大的离谱,基本上就是“不可用状态”。

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

    排序法最差时间分析平均时间复杂度稳定度空间复杂度

    冒泡排序O(n2)O(n2)稳定O(1)

    快速排序O(n2)O(n*log2n)不稳定O(log2n)~O(n)

    选择排序O(n2)O(n2)稳定O(1)

    二叉树排序O(n2)O(n*log2n)不一顶O(n)

    插入排序O(n2)O(n2)稳定O(1)

    堆排序O(n*log2n)O(n*log2n)不稳定O(1)

    希尔排序OO不稳定O(1)

    展开全文
  • 有穷性:一个算法必须总在执行有穷步之后结束,且每一步都可在有穷时间内完成 注:算法必须是有穷的,而程序可以是无穷的(排队系统就是一个程序,可以不停歇) 确定性:算法中每条指令必须有确切的含义,对于相同的...

    数据结构

    • 用程序代码把现实世界的问题信息化
    • 用计算机高效处理这些信息,从而创造价值
      在这里插入图片描述

    数据
    数据是信息的载体,是描述客观事物属性的数,字符及所有能输出到计算机中不能被计算机程序识别和处理(0和1二进制)的符号集合
    数据元素,数据项
    数据元素是数据的基本单位,通常作为一个整体进行考虑和处理。
    一个数据元素可以由若干数据项组成,数据项是构成数据元素不可分割的最小单位
    例:
    在这里插入图片描述

    数据结构,数据对象
    数据结构:相互之间存在一种或多种特定关系的数据元素的集合
    数据对象:具有相同性质的数据元素的集合,是数据的一个子集
    例:
    数据结构:某个特定门店的排队顾客信息和它们之间的关系
    数据对象:全国所有门店的排队顾客信息的集合

    数据结构的三要素:
    数据的逻辑结构–元素之间的逻辑关系是什么?

    • 集合:各个元素同属于一个集合,无其他关系
    • 线性结构:数据元素之间是一对一的关系,除了第一个元素,所有元素都有唯一前驱,除了最后一个元素,所有元素都有唯一后继
    • 树形结构:数据元素之间是一对多的关系
    • 图结构:数据元素之间是多对多的关系(微信好友)

    数据的物理结构–如何用计算机表示数据元素的逻辑关系

    为什么顺序存储查找快,链式存储查找慢?
    因为顺序存储向排队,按照对应位置就是对应的元素,在物理存储中是一片连续的空间,而链式存储只有元素知道下一个元素所在的位置,要顺序访问每一个前驱
    

    数据的运算–施加在数据上的运算,包括运算的定义和实现,运算的定义是针对逻辑结构的,运算的实现是针对存储结构,指出运算的具体操作步骤。

    数据类型,抽象数据类型
    数据类型是一个值得集合和定义在此集合上的一组操作的总称

    1. 原子类型:其值不可再分的数据类型
      例;
      boolean类型类型
      值的范围: true,false
      可进行操作:与或非
    2. 结构类型:其值可以在分解为若干成分(分量)的数据类型
      例:
      typedef struct Point
      {
      int x;
      int y;
      struct Point* next;
      } Point;

    抽象数据类型:抽象数据组织及与之相关的操作
    ADT:用数学化的语言定义数据的逻辑结构,定义运算,与具体的实现无关

    算法

    在这里插入图片描述

    算法定义:

    如何处理数据,以解决实际问题

    算法的特性

    1. 有穷性:一个算法必须总在执行有穷步之后结束,且每一步都可在有穷时间内完成
      注:算法必须是有穷的,而程序可以是无穷的(排队系统就是一个程序,可以不停歇)
    2. 确定性:算法中每条指令必须有确切的含义,对于相同的输入只能得出相同的输出
    3. 可行性:算法中描述的操作都可以通过已经实现的基本运算执行有限次来实现。
    4. 输入:一个算法有零个或多个输入,这些输入取自于摸个特定的对象的集合
    5. 输出:一个算法有一个或多个输出,这些输出是与输入有着某种特定关系的量

    好算法的特点

    • 正确性:算法应能够正确解决求解问题
    • 可读性:算法应具有良好的可读性,帮助人们理解
    • 健壮性:输入非法数据时,算法能适当地作出反应或进行处理,不会产生莫名其妙的输出
    • 高效率和低存储量的需求(高效率:执行速度快,时间复杂度低)(低存储量:空间复杂度低)

    时间复杂度

    常数时间的操作:
    一个操作如果和样本的数据量没有关系,每次都是固定时间内完成的操作,叫常数操作,时间复杂度为一个算法流程中常数操作数量一个指标
    n个数的排序算法

    1. 先从0到n-1位找最小的数,需要查找n次(数组寻址),每次需要比较n-1次,1次交换操作,所以整个算法的常数操量可以写为an^2+bn+c (时间复杂度为O(n^2))
      注意:数组的寻址操作是和数据量无关的,可以是常数项操作,集合是链表,其遍历操作是和数据量有关的,不是常数操作

    评价一个算法流程的好坏,先看时间复杂度的指标,然后再分析不同数据样本下实际运行的时间,叫“常数项时间”
    额外空间复杂度:一个算法在运行过程中临时占用存储空间大小的量度,即,需要多少额外的磁盘空间来维持整个算法的运行
    算法1:

    void loveYou(int n){//n为问题的规模
    	int i=1;
    	while(i<=n){
    		i++;
    		printf("%d\n",i);
    	}
    	printf("%d",n);
    }
    

    单循环:时间开销与问题规模n的关系–>T(n)=3n+3=O(n)
    结论1:顺序执行的代码只会影响常数项,可以忽略
    结论2:只需找循环中的一个基本操作分析其只需次数与n的关系即可

    算法2:

    void loveYou(int n){//n为问题的规模
    	int i=1;
    	while(i<=n){//此处需要执行n+1次,因为最好还要比较i=n+1时的情况
    		i++;
    		printf("%d\n",i);
    		for(int j=1;j<=n;j++){
    			printf("%d",j);
    		}
    	}
    	printf("%d",n);
    }
    

    时间开销与问题规模n的关系:
    T(n)=O(n)+O(n^2) = O(n^2)
    结论3:如果有多层嵌套循环只需要关注最深层循环了几次即可。
    算法3

    void loveYou(int n){//n为问题的规模
    	int i=1;
    	while(i<=n){
    		i*=2;//每次翻倍 i=2,4,6
    		printf("%d\n",i);
    	}
    	printf("%d",n);
    }
    

    计算上述算法的时间复杂度T(n):
    设最深层循环的语句频度(总循环的次数)为x,则有循环条件可知,循环结束时刚好满足2^x>n
    x=log2^n+1
    T(n)=O(x)=O(log2^n)

    void loveYou(int flag[],int n){//n为问题的规模
    	for(int i=0;i<n;i++){//从第一个元素开始查找
    		if(flag[i]==n){//找到元素n
    			printf("%d\n",n);//flag数组中乱序存放1~n这些数
    			break;
    		}
    	}
    }
    

    计算上述算法的时间复杂度T(n)
    最好情况:元素n在第一个位置 --时间复杂度为T(n)=O(1)
    最坏情况:元素n在最后一个位置 --最坏时间复杂度T(n)=O(n)
    平均情况:假设元素n在任意一个位置的概率相同为1/n --平均时间复杂度T(n)=O(n)
    循环次数x=(1+2+3+4+…+n)1/n=(1+n)/2
    在这里插入图片描述

    空间复杂度

    算法1

    void loveYou(int n){//n为问题的规模
    	int i=1;
    	while(i<=n){
    		i++;
    		printf("%d\n",i);
    	}
    	printf("%d",n);
    }
    

    无论问题规模怎么变,算法运行所需的内存空间都是固定的常量,算法空间复杂度为
    S(n)=O(1)
    算法原地工作–算法所需内存空间为常量
    在这里插入图片描述
    算法2:

    void test(int n){
    	int flag[n];//声明一个长度为n的数组
    	int i;
    }
    

    假设在该计算机中一个int变量占4b
    则所需的内存空间为4+4n+4=4n+8
    S(n)=O(n)
    算法3

    void test(int n){
    	int flag[n][n];//声明一个长度为n*n的数组
    	int i;
    }
    

    二维数组所需的空间是4n^2
    S(n)=O(n^2)
    算法4

    void loveYou(int n){
    	int a,b,c;//声明一系列局部变量
    	if(n>1){
    		loveYou(n-1);
    	}
    	printf("%d\n",n);
    }
    

    空间复杂度=递归调用深度
    S(n)=O(n)
    函数的递归调用,空间复杂度为44n B

    线性表

    (在考虑数据的逻辑结构的时候不用考虑数据元素的类型,用圆圈代替每个元素,例如,线性表,一张表每一行都是一个数据元素,o-o-o-o-o-o-o-o这样的逻辑结构,而具体实现这种逻辑的物理结构可以是链表也可以是顺序表)
    定义(逻辑结构):线性表是具有相同(每个数据元素所占空间一样大)数据类型的n(n>=0)个数据元素的有限序列(有次序),其中n为表长,的那个n=0时线性表是一个空表。若用L命名线性表,一般表示为L=(a1,a2,…,an)
    ai是线性表中的“第i个”元素,线性表中的位序"位序是从1开始的,而数组下标是从0开始的"
    基本操作(运算)
    a1是表头元素,an是表尾元素
    除第一个元素外,每个元素有且仅有一个直接前驱,除了最后一个元素外,每个元素有且仅有一个直接后继
    在这里插入图片描述什么时候需要传入引用类型的参数:当需要返回修改后的参数,则传入引用类型(类似java中的数组)

    顺序表

    顺序表–用顺序存储的方式实现线性表顺序存储,把逻辑上相邻的元素存储在物理空间上也相邻的存储单元中,元素之间的关系由存储单元的邻接关系来体现

    假使线性表第一个元素存放位置是LOC(L),则第二个元素存放的位置是LOC(L)+数据元素的大小
    如何知道一个数据元素大小:c语言中有一个方法sizeof(ElemeType)
    顺序表的实现–静态分配
    在内存中所占的大小为sizeof(int)*MaxSize,第i个元素位置为,第一个元素位置+sizeof(int)*i

    #include <stdio.h>
    #define MaxSize 10 //定义最大长度
    
    typedef struct{
    	int data [MaxSize];//用静态的数组存放数据元素
    	int length;//顺序表的当前长度
    }SqList;//顺序表的类型定义
    //定义基本操作--初始顺序表
    void InitList(SqList &L){
    	for(int i=0;i<MaxSize;i++){
    		L.data[i]=0;//将所有数据元素设置为默认初始值
    		L.length=0;//顺序表初始长度对0
    	}
    }
    int main()
    {
    	SqList L;//申明一个顺序表
    	InitList(L);//初始化顺序表
    	return 0;
    
    }
    

    | 仅c++支持此种写法
    顺序表实现–动态分配
    在这里插入图片描述顺序表的特点

    1. 随机访问,即:可以在O(1)时间内找到第i个元素。(代码实现:data[i-1];静态分配,动态分配都一样)
    2. 存储密度高,每个节点只存储数据元素(链式存储需要存放指针)
    3. 拓展容量不方便(即便采用动态分配的方式实现,拓展长度的时间复杂度也比较高)
    4. 插入、删除操作不方便,需要移动大量的元素

    顺序表的插入操作
    在这里插入图片描述对插入数据进行合法性判断
    在这里插入图片描述插入操作的时间复杂度
    在这里插入图片描述
    顺序表的删除元素
    在这里插入图片描述顺序表删除数据元素的时间复杂度
    在这里插入图片描述顺序表的查找
    静态分配方式:

    typedef struct{
    	ElemType data[MaxSize];//用静态的“数组”存放数据元素
    	int length;//顺序表当前长度
    }SqList;//顺序表的类型定义(静态分配方式)
    
    ElemType GetElem(SqList L,int i){
    	return L.data[i-1];
    } 
    

    动态分配的方式:

    #define InitSize 10//顺序表的初始长度
    typedef struct{
    	ElemeType *data;//指示动态分配数组的指针
    	int MaxSize;//顺序表的最大容量
    	int lengthl//顺序表的当前长度
    }SqList;//顺序表的类型定义(动态分配方式)
    
    ElemType GetElem(SqList L,int i){
    	return L.data[i-1];
    } 
    

    时间复杂度为O(1)
    按值查找位序

    #define InitSize 10//顺序表的初始长度
    typedef struct{
    	ElemeType *data;//指示动态分配数组的指针
    	int MaxSize;//顺序表的最大容量
    	int lengthl//顺序表的当前长度
    }SqList;//顺序表的类型定义(动态分配方式)
    //在顺序表L中查找第一个元素值等于e的元素,并返回其位序
    ElemType LocalElem(SqList L,int i){
    	for (int i=0;i<L.length;i++)
    		if(L.data[i]=e)
    			return i+1;
    	return 0
    } 
    

    最好情况:第一个元素就是查找的元素O(1)
    最好情况:O(n)
    平均情况:1/n*1+…

    展开全文
  • 一、算法的时间复杂度定义在进行算法分析时,语句总的执行次数T(n)是关于问题规模n的函数,进而分析T(n)随n的变化情况并确定T(n)的数量级。算法的时间复杂度,也就是算法的时间量度。记作:T(n)=O(f(n))。它表示随...
  • 时间复杂度和空间复杂度算法效率时间复杂度大O渐进表示法(估算)空间复杂度 什么是数据结构? 数据结构(Data Structure)是计算机存储、组织数据的方式,指相互之间存在一种或多种特定关系的数据元素的集合。 什么是...
  • 算法的时间复杂度

    2021-10-17 17:29:02
    衡量算法的好坏有很多的指标,其中最重要的就是算法的时间复杂度和空间复杂度 。这一节主要说算法的时间复杂度时间复杂度可直观理解为代码执行时间的长短。实际上,由于受运行环境和输入规模的影响,代码的绝对...
  • 常见排序算法及其对应的时间复杂度、空间复杂度: 排序算法经过长时间演变,大体可以分为两类:内排序和外排序。在排序过程中,全部记录存放在内存,则成为内排序;如果排序过程中需要使用外存,则称为外排序,本文...
  • 时间复杂度计算

    2021-07-25 00:43:23
    时间复杂度计算算法的运行时间是指一个算法在计算机上运算所花费的时间。它大致等于计算机执行简单操作(如赋值操作,比较操作等)所需要的时间与算法中进行简单操作次数的乘积。通常把算法中包含简单操作次数的多少...
  • 排序算法及其时间复杂度

    千次阅读 2021-03-16 21:35:16
    1. 排序算法时间复杂度 稳定:如果a原本在b前面,而a=b,排序之后a仍然在b的前面; 不稳定:如果a原本在b的前面,而a=b,排序之后a可能会出现在b的后面; 内排序:所有排序操作都在内存中完成; 外排序:由于数据太...
  • 快速排序最好的情况下:每次平分子数组,时间复杂度为Nlog2N, 空间复杂度主要为递归调用的...快速排序最差的情况下,每次两个子数组的大小都为1,n-1,意味着退化为冒泡排序,时间复杂度为N^2,空间复杂度为N。 ...
  • 各种排序算法比较各种常用排序算法类别排序方法时间复杂度空间复杂度稳定性复杂性特点最好平均最坏辅助存储简单插入排序直接插入O(N)O(N2)O(N2)O(1)稳定简单希尔排序O(N)O(N1.3)O(N2)O(1)不稳定复杂选择排序直接选择...
  • 转载请注明出处:排序算法经过了很长时间的演变,产生了很多种不同的方法。对于初学者来说,对它们进行整理便于理解记忆显得很重要。每种算法都有它特定的使用场合,很难通用。因此,我们很有必要对所有常见的排序...
  • 基本思想:两两比较待排序数据元素的大小,发现两个数据元素的次序相反时即进行交换,直到没有反序的数据元素为止。2.排序过程:设想被排序的数组R[1..N]垂直竖立,将每个数据元素看作有重量的气泡,根据轻气泡不...
  • 还在头疼时间复杂度如何计算?来看下本文,彻底学会时间复杂度问题的求解。
  •    在链表中查找第 n 个数据以及查找指定的数据的时间复杂度是 O(N) ,但是插入和删除数据的时间复杂度是 O(1) ,因为只需要调整指针就可以 栈: 栈(stack)又名堆栈,它是一种运算受限的线性表。限定仅在表尾...
  • 常用的时间复杂度常数阶\(O(1)\)说明: 只要代码中没有复杂的循环条件,无论代码的函数是多少,一律为常数阶\(O(1)\)int i=1;int j=3;int m=0;m=i+j;....对数阶 \(O(log_2n)\)说明: 存在循环体,在不考虑循环体的...
  • 文章目录 0 笔记说明 1 基本知识 1.1 数据结构三要素 1.2 算法的五大特性 1.3 设计算法考虑这些 2 复杂度 2.1 时间复杂度 2.2 空间复杂度 0 笔记说明 来源于2020 王道考研 数据结构,博客内容是对自己笔记的书面整理...
  • 由于不必须按顺序存储,链表在插入的时候可以达到O(1)的复杂度,比另一种线性表顺序表快得多,但是查找一个节点或者访问特定编号的节点则需要O(n)的时间,而顺序表相应的时间复杂度分别是O(logn)和O(1)。使用链表...
  • } 运行结果: 时间复杂度 堆排序的时间复杂度,主要在初始化堆过程和每次选取最大数后重新建堆的过程; 初始化建堆过程时间:O(n) 推算过程: 首先要理解怎么计算这个堆化过程所消耗的时间,可以直接画图去理解; ...
  • 1 如何评价、分析一个排序算法?很多语言、数据库都已经封装...分析一个排序算法,主要从以下3个方面入手:1.1 排序算法的执行效率1)最好情况、最坏情况和平均情况时间复杂度待排序数据的有序度对排序算法的执行效率...
  • //------------------>摘自:...渐进时间复杂度 比如算法A的相对时间是T(n)= 100n,算法B的相对时间是T(n)= 5n^2,这两个到底谁的运行时间更长一些?这就要...
  • 对于各位不想看文字的朋友,这个系列会配套视频, B 站视频地址:「一本正经的聊数据结构(1):时间复杂度」欢迎各位同学关注以及素质三连。引言最近有好多同学一直问我一些基础的问题,想了想,还是抄抄冷饭,聊聊...
  • 所以得出的结果为:T[n] = O( nlogn ) 因为不管元素在什么情况下都要做这些步骤,所以花销的时间是不变的,所以该算法的最优时间复杂度和最差时间复杂度及平均时间复杂度都是一样的为:O( nlogn );好像有人说最差...
  • 7.1 排序算法的介绍 排序也称排序算法(Sort Algorithm),排序是将一组数据,依指定的...7.3 算法的时间复杂度 7.3.1度量一个程序(算法)执行时间的两种方法 1) 事后统计的方法 这种方法可行, 但是有两个问题:一是要.
  • 最近,笔者学习了冒泡排序,在此简单分享一下。冒泡排序的原理:对于一个数组,...如果有n个元素,则第一次循环进行n-1次,第二次循环进行n-2次,…………,第n-j次循环过后,会按大小顺序排出j个较大的数。持续以上...
  • 保姆级教学!彻底学会时间复杂度和空间复杂度

    千次阅读 多人点赞 2021-08-19 18:37:13
    两个月斩获 70k star,前字节大神刷题笔记 清华学霸的刷题笔记(leetcode最优解) 常见时间复杂度 算法学习过程中,我们会遇到各种各样的时间复杂度,但纵使你代码七十二变,几乎也逃不过下面这几种常见的时间复杂度...
  • 数据结构时间复杂度

    2021-05-27 20:05:31
    时间复杂度掌握顺序表的CRUD操作--顺序表:模仿ArrayList顺序表中:新增和删除都需要挪动元素复杂度分析什么是复杂度分析?复杂度分析的过程中:一般情况下,排除硬件的影响复杂度分析分为两个:1.1 时间复杂度1.1.1...
  • 时间复杂度 首先一点关键的是,ArrayList的内部实现是基于基础的对象数组的,因此,它使用get方法访问列表中的任意一个元素时(random access),它的速度要比LinkedList快。LinkedList中的get方法是按照顺序从列表的...
  • } 快速排序的时间复杂度为O(nlogn),最坏时间复杂度为O(n^2),最坏的情况适之每次区间划分的结果都是基准关键字的最左边或者右边,即选择的数字是待排序列中最小或者最大的。当n较大时使用较好。 2.归并排序 归并...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 127,941
精华内容 51,176
关键字:

时间复杂度的大小顺序