Closest Pair of Points (Divide and Conquer) Explained
Вставка
- Опубліковано 24 сер 2024
- This is a recorded presentation for a college course (CMPU241, Spring 2021).
Algorithm explained: Closest Pair of Points (using the Divide and Conquer method)
Time & Space complexity: O(nlgn)
probably the clearest explanation I've seen of this algorithm thanks!
OMG there hasn't been any explanation better than yours ever!!!! couldn't be any clearer!!!!! Thank you so much!!!
Truly an on "point" explanation. Thank you, keep going!
That was the nicest video of this algorithm on YT so far, keep it up
The way you explained is really awesome. Can we expect more videos like this?
no bc
we definitely need more of these explanations from you
You have explained the topic very effectively and you made everything easy. Before I had plenty of doubts but now you made it clear. Keep on posting such videos. I'll be eagerly waiting for your next videos ^_^
What are best average and worst time complexity of this algorithm called closest pair by divide and conquer
Incredible explanation, the best I have found, thank you very much!!!!!!!!!!!!!!!!!!!!!!!!!
Clear and precise explanation with a lovely voice.
The only tutorial on the channel had to be the on the topic i was looking for.
讲得太好了，非常清晰。Visualization is awesome.
Thank you so much ,
I wanted to bring to your attention a concern I have regarding the time complexity of the closestPair function in this algorithm.
Specifically, when calling the function for all elements of Y in the following lines:
dl = closestPair(X[1 .. mid], Y);
dr = closestPair(X[mid+1 ... n], Y);
I believe this approach increases the time complexity. The search for the strip is performed in Y, which has a length of N. Consequently, the work done by subproblems becomes O(N), where N is the number of all the points of the problem. This happens because Y is not getting smaller through the dividing process.
I propose a modification where the work by subproblems is O(L), where L is the length of the subproblem. To achieve this, the Y in the call to closestPair(X, Y) should contain the same elements as X, with X being the array that undergoes division.
Thank you for considering this suggestion.
Wow, amazing video! You explained it so well that I finally understood it after breaking my head for sooo many days. Thanks a ton! 🙏🙏
The Best Explaination ever, you should join some college as an advanced algorithm Professor.
Thank you so much for such a nice explanation :))
+1 @Mayank Kumar
+1 ansh arora
@@mohitmridul6164 +1
@Mayank Kumar +1
Ha bhaiya.
It helped a lot .
Maza aa gaya 🤗🤗
wow this was amazing. thank you so much for this!!
Quality content, I was looking for. Thank you!
the best explanations I've ever seen
Thank you so much, best explanation I’ve come across!
amazing amazing amazing and the best explanation for this problem. Thank you
Simple and to the point. Nicely done.
Fantastic video! Best explanation I have seen so far. Would be awesome to see more videos on other algorithms. Thank you!
This is amazing. Please make more videos on other algorithms!!
so great , that was i am loving version.
This is so good. Thank you!!
Beautiful algorithm explained by a beautiful voice
very very nice explanantion....
Fantastic presentation! Thanks a bunch! :)
Great explanation, thank you! But I think the time complexity of pseudo code provided isn't obviously O(n log n) due to the step of selecting S from whole Y. Since you pass the whole Y in each call, the "n" isn't split into halves when recursion, but n -> 2n -> 4n -> ... where n is the length of X. I think it could be done in O(n) by merging the Y-sorted sub-arrays from divided problems.
yes, this is correct. The recursive calls must be made with 2 modified Ys. One for the left points and one for the right. Or, as you suggest, by merging the points. To merge them, you would need to return not only d, but also the points merged by y coordinate
great explanation, thank you
Wow great video! I had a hard time to understand why there was a maximum number of point in the delta region. Thank you
Very visual and clear explanation thank you so much!
Thank you, very nicely explained!
Best explanation, bar none
Amazing explanation 🤩🤩 the animation was extremely helpful in seeing how the algorithm works
This was perfect.....Thank you so much!
It's really a clear explaination, amazing !
That was awesome
Keep it going🎉🎉
Thank you! Great explanation!
Excellent work and very easy to understand
I think it's enough to iterate j from 1 to 4 because in each side the maximum number of points is 4
the best explanation ever
This is an amazing explanation! 讲得好棒！
Amazing thank you for your explanation !!!!
Cleanest explanation ❤️
Pretty clear. Thank you.
Code in c++ :
#include
#include
using namespace std;
bool compare(paira , pairb)
{
return a.second=e)return LONG_MAX;
if(e-s+1==2)
{
long d = dis(x[e],x[s] ) ;
return d ;
}
int mid = (s+e)/2 ;
long l = fun(x, s, mid) ;
long r = fun(x,mid+1 , e ) ;
long d = min(l,r) ;
vector arr ;
for(int i =s ; i= x[mid].first-d and x[i].first n;
pair* arr = new pair[n];
for(int i = 0; i < n; ++i)
{
cin >> arr[i].first >> arr[i].second;
}
cout
amazing work. helped me a lot
thank you! Very well explained!
5:57 Why for j=1 to 7? what's the 7 about?
God Bless you, you are great
wouldn't it throw an error if there are only less than 7 points within the strip? The program would be accessing a an array index greater than its length
Thank you! :D
Great explanation !
Great explanation mam.
i have a question. does the question assume there are coincident points? if coincident points arent allowed, then when checking in the 2d * d rectangle, can we just check for the next 5 points instead of 7? since coincident points will not happen. thanks.
how did she arrived at the 2nd strip
Please make more videos🥲
If possible please create a whole series of your lectures.
how did you find delta in 6,8 do you brute force the left and the right with out divide it ?
thanks a lot for your explanation
講的很好！😊
For split pairs why we iterating 1 to 7?
3:35 2-delta distance
4:08 2d*d O(1) for each point
Well explained!
tysm it makes so much more sense now lol
Thank you!
best explanation
thank you
this is such a good and clear explanation, do you mind if I use it for teaching?
thanks. useful.
感恩
Peeps who are here for BUET-18's offline-8 comment here
hey bro 🙂
kere mama mmk
Hola🥲
Yo....bro
hehe
Thanks
Great Explanation but i have not understood clearly
3:55
7 points explanation
Can you do more videos, please?
First of all i was on a thought she will definitely waste my time but u nailed it 🔥
الله يدخلش الجنة يارب
now find the optimal solution for N-dimensional Euclidean space.
Can we expect some more videos?
W vid
8:00 Y sorted points also need to be halved before recursion to ensure optimal complexity, right? This can be done via (id) based filtering of Y into Y_left & Y_right based on a HashSet representation of what goes into X_left & X_right.
Am I missing something? Great explanation otherwise :)
Who told you the brute force solution was n squared?
Once a test has been performed, it can be tagged as done. Then that pair test does not need to be done again.
Consider 4 points; 1,2 3,4
1 needs to test 2,3,4
2 only needs to test 3,4 (because 1,2 test is already done))
3 only needs to test 4
That is only 6 tests need to be performed, not 16 (n squared)
Formula is probably factorial n...
Please get gour facts right!
Consider 5 points, 100 points, 10000 points, and let me know if you still think the formula is factorial n (hint: sum of arithmetic sequence).
Then please get your fact right about Big O Notation! Keep in mind that constants are dropped when calculating time complexity.
In that case the running time would be something like n(n-1) + (n-1)(n-2) + ... + (n-k+1)(n-k) = (n^2-n) + (n^2-3n+2) + (n^2+(1-2k)n+(k^2-k)) = kn^2 + a. Where a is the sum of other lower power terms. Since big O notation drops those lower terms and constants we get that big o notation is n^2.
@@marceloenciso6665 agreed, sorry its not factorial, the formula for total number of tests is;
(n squared -n) /2
So the total number of tests will always be less than HALF of n squared
Anyway this divide and conquer method it still a poor way of solving the problem.
Doing all those square roots is a real mess. This is how I would do it for least amount of CPU cycles;
1. Brute force all points but only testing points AFTER the point. (N squared -n) /2 tests;
1a. Get the x dist and y dist (very fast, just 2 subtractions needed)
1b. keep the larger of the two, very fast (we will call this the simple distance)
1c. Put the simple distance in a list, ordered by size (very fast)
TRICK; The actual distance can never be more than the simple distance *1.41 so only need to test those list entries that are LESS then the smallest entry *1.41
Now we are only needeing to do the mults and sq roots on a tiny percentage of the point pairs;
2. Process down the ranked list;
2a. Do the pythag mult mult sq root etc to get real dist
2b. If less than prev best, save that as best
2c. If the list entry is >top entry *1.41 then job is done!
Ive been coding high perf algorithms for 30 years and mostly had to do it on low perf 8bit systems with no math processor etc. The algorithm I outlined above is just my first attempt but would be far quicker than the divide and conquer system provided that n is not excessively large.
Ok, i just wrote some quick c code to test my algorithm.
n = 100 points, randomly distributed x and y values using; random(1024)
Brute force ranked point distances by my "simple distance" ie the largest of x1-x2 or y1-y2 (4950 tests)
Then ONLY needed to do the pythag mult sqroot etc on ANY points where; simple dist
@@wizrom3046
You should really learn about big O notation before saying anything.
(n squared - n) / 2 -> (n^2) /2 - n/2 -> n^2*1/2 - n*1/2
When we calculate big O notation, we only care about the *dominant terms* and we do not care about the coefficients. Thus we take the n squared as our final big O (in this case n^2 is the dominant term and you can eliminate all the other parts in the big O notation).
牛逼 上课没听懂在你这里听懂了