复杂性（计算大O）
我一直在解决教科书中的一些问题，这些问题是关于计算算法的大 O 复杂度的。我遇到的一个问题在后面没有答案，我将不胜感激。
您有一个长度为 n-1 的数组，其中包含包含单词列表的链接列表。每个链表首先进行插入排序，然后使用链表中的第一个单词对数组进行快速排序。这个算法的大O复杂度是多少？
我已经知道：
遍历链表是 O(n) 插入排序是 O(n^2) 快速排序是（nlogn）
我只是不确定如何计算整个算法的复杂性
I've been working through some problems in my textbook that are about calculating the big O complexity of algorithms. One of the questions i'm stumped on doesn't have an answer in the back and i'd appreciate any input.
You have an array of length n-1 containing linked lists that contain lists of words. Each linked list is first insertion sorted and then using the first word in the linked list, the array is quicksorted. What is the big O complexity of this algorithm?
I already know that:
Traversing a linked list is O(n)
insertion sort is O(n^2)
Quick Sort is (nlogn)
I'm just not sure how to go about calculating the complexity of the whole algorithm
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
“每个链表首先进行插入排序”
这使得复杂度为
O(n) * O(m^2)或O(n*m^2)- 我们必须使用不同的字母，因为每个列表的长度与列表的数量无关。“然后对数组进行快速排序”
这增加了
O(n log n)。总计：
O(n*m^2 + n log n)，简化为O(n*m^2)（n log n与n*m^2相比，code> 并不重要）。"each linked list is first insertion sorted"
This makes for a complexity of
O(n) * O(m^2), orO(n*m^2)- we have to use a different letter because the length of each list is not related to the number of lists."then the array is quicksorted"
That adds
O(n log n).Total:
O(n*m^2 + n log n), which simpifies toO(n*m^2)(then log nis not significant compared to then*m^2).