建立一个有n个元素的有序单链表的时间复杂度度为什么是O(n^2) 求详解哇……(>﹏<)

Question

如题所述

Answer 1

因为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表示它是指向某一结点的指针。

Answer 2

因为o(n^2) ,对单链表而言，一些快速的排序算法，不能用，只能用直接插入等o(n^2) 级的排序算法来实现排序。因为是有序单链表那么每次插入到链表尾结点，那么每次插入都要从头扫到尾，然后1+2+3+... m = O(m^2)这样。

有序链表就是，从头结点开始到链表结尾，节点中数据有序排列，比如说递增，递减或者其他满足一定条件的规则。单向链表（单链表）是链表的一种，其特点是链表的链接方向是单向的，对链表的访问要通过顺序读取从头部开始；链表是使用指针进行构造的列表；又称为结点列表，因为链表是由一个个结点组装起来的；其中每个结点都有指针成员变量指向列表中的下一个结点；

列表是由结点构成，head指针指向第一个成为表头结点，而终止于最后一个指向nuLL的指针。

本回答被网友采纳

Answer 3

创建单链表的时间复杂度是O(n)，而要创建有序的单链表，则每生成一个新节点时都要与已存在的结点进行比较，确定恰当的插入位置，因此时间复杂度是O(n^2)。

Answer 4

单链表创建的时间复杂度是O(n)，而要建立一个有序的单链表，则每生成一个新结点时需要和已有的结点进行比较，确定合适的插入位置，所以时间复杂度是 O(n2)。

Answer 5

这个问题本身就是错的，创建一个有序的单链表，时间复杂度是O(n)。