pdist time complexity and inner working
显示 更早的评论
What is the time complexity of pdist, how does it calculate different distances between sets of points?
The documentation for pdist does not include anything about the complexity and its internal workings, could someone please guide me as to where to find this information.
Thank you in advance.
采纳的回答
Walter Roberson
2022-11-7
0 个投票
You can read the source code.
For most of the distance measures a loop is done over elements of the array, picking out a particular point and calculating the distance to the remaining points after it. So (N-1) distances the first time, then N-2 for second iteration, then N-3 and so on down to 1. Time is the sum of those, 1 to N-1, which is N*(N-1)/2 which is O(N^2)
You might possibly want to define it more strictly as O(d*N^2) where d is the dimension of the points.
There are no advanced algorithms involved. No quadtree, for example, that might hypothetically reduce the number of comparisons for cityblock to lower than d (the dimension). No removal of duplicate locations is done (detection of duplicates would be O(n*log(n)*d) and you would still need O(N^2) after)
更多回答（0 个）
类别
在 帮助中心 和 File Exchange 中查找有关 Data Clustering 的更多信息
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!
Translated by 
