理解嵌套分类的时间复杂性
原标题：Understanding Time complexity of nested sorting
I am solving this LeetCode problem 1636. Sort Array by Increasing Frequency:
Given an array of integers nums, sort the array in increasing order based on the frequency of the values. If multiple values have the same frequency, sort them in decreasing order.
Return the sorted array.
I wrote the following working code:
class Solution:
def frequencySort(self, nums: List[int]) -> List[int]:
ddict = Counter(nums)
ddict = dict(sorted(ddict.items(), key=lambda x:(x[1], x[0])))
defDict = defaultdict(list)
res = []
for k, v in ddict.items():
defDict[v].append(k)
del(ddict)
for k, v in defDict.items():
v.sort(reverse=True)
for val in v:
for _ in range(k):
res.append(val)
return res
I think it has a time complexity of O(n.(nlog(n)), because I am sorting each list in defaultdict for every key in the worst case.
But the time complexity analysis in LeetCode as well as AI tools like chatGPT and Perplexity AI find the time complexity to be O(nlog(n)). I am confused. Can anyone please help me understand why it s not O(n.(nlog(n))?
最佳回答
Sorting distinct chunks of data will still amount to O(?log?). For instance, let s say you have ? keys in defDict, where each has a list (v) that has an average length of ?/?, then sorting each of these v will amount to a complexity of O(? (?/?)log(?/?)), which is O(?log(?/?)), which is not worse than O(?log?).
Note that your v is already sorted in ascending order before the call to v.sort is made, and you could just have reversed v. As Python s native sort (timsort) deals well with such input, it will run in O(?) where ? is the size of v, which means this part of your algorithm represents O(?) as time complexity, making the initial sort the determining step for what concerns the overall time complexity: O(?log?).
问题回答
暂无回答
相关问题
How to add/merge several Big O s into one
If I have an algorithm which is comprised of (let s say) three sub-algorithms, all with different O() characteristics, e.g.:
algorithm A: O(n)
algorithm B: O(log(n))
algorithm C: O(n log(n))
How do ...
Finding the spin of a sphere given X, Y, and Z vectors relative to sphere
I m using Electro in Lua for some 3D simulations, and I m running in to something of a mathematical/algorithmic/physics snag.
I m trying to figure out how I would find the "spin" of a sphere of a ...
Grokking Timsort
There s a (relatively) new sort on the block called Timsort. It s been used as Python s list.sort, and is now going to be the new Array.sort in Java 7.
There s some documentation and a tiny Wikipedia ...
Manually implementing high performance algorithms in .NET
As a learning experience I recently tried implementing Quicksort with 3 way partitioning in C#.
Apart from needing to add an extra range check on the left/right variables before the recursive call, ...
Print possible strings created from a Number
Given a 10 digit Telephone Number, we have to print all possible strings created from that. The mapping of the numbers is the one as exactly on a phone s keypad.
i.e. for 1,0-> No Letter
for 2->...
Enumerating All Minimal Directed Cycles Of A Directed Graph
I have a directed graph and my problem is to enumerate all the minimal (cycles that cannot be constructed as the union of other cycles) directed cycles of this graph. This is different from what the ...
Find number of permutations of a given sequence of integers which yield the same binary search tree
Given an array of integers arr = [5, 6, 1]. When we construct a BST with this input in the same order, we will have "5" as root, "6" as the right child and "1" as left child.
Now if our input is ...
Quick padding of a string in Delphi
I was trying to speed up a certain routine in an application, and my profiler, AQTime, identified one method in particular as a bottleneck. The method has been with us for years, and is part of a "...
