建立一个有n个元素的有序单链表的时间复杂度度为什么是O(n^2) 求详解哇……(>﹏<)
因为o(n^2),对单链表而言,一些快速的排序算法,不能用,只能用直接插入等o(n^2)级的排序算法来实现排序。因为是有序单链表那么每次插入到链表尾结点,那么每次插入都要从头扫到尾,然后1+2+3+... m = O(m^2)这样。
链表中的数据是以结点来表示的,每个结点的构成:元素(数据元素的映象) +指针(指示后继元素存储位置),元素就是存储数据的存储单元,指针就是连接每个结点的地址数据。以“结点的序列”表示线性表称作线性链表(单链表),单链表是链式存取的结构。
扩展资料:
typedef char DataType; //假设结点的数据域类型为字符
typedef struct node{ //结点类型定义
DataType data; //结点的数据域
struct node *next;//结点的指针域
}ListNode;
typedef ListNode *LinkList;
ListNode *p;
LinkList head;
注意:
①LinkList和ListNode是不同名字的同一个指针类型。(命名的不同是为了概念上更明确)
②*LinkList类型的指针变量head表示它是单链表的头指针。
③ListNode类型的指针变量p表示它是指向某一结点的指针。
因为o(n^2) ,对单链表而言,一些快速的排序算法,不能用,只能用直接插入等o(n^2) 级的排序算法来实现排序。因为是有序单链表那么每次插入到链表尾结点,那么每次插入都要从头扫到尾,然后1+2+3+... m = O(m^2)这样。
有序链表就是,从头结点开始到链表结尾,节点中数据有序排列,比如说递增,递减或者其他满足一定条件的规则。单向链表(单链表)是链表的一种,其特点是链表的链接方向是单向的,对链表的访问要通过顺序读取从头部开始;链表是使用指针进行构造的列表;又称为结点列表,因为链表是由一个个结点组装起来的;其中每个结点都有指针成员变量指向列表中的下一个结点;
列表是由结点构成,head指针指向第一个成为表头结点,而终止于最后一个指向nuLL的指针。
2021-06-26
这个问题本身就是错的,创建一个有序的单链表,时间复杂度是O(n)。