Closest Pair of Points (Divide and Conquer) Explained
Vložit
- čas přidán 3. 05. 2021
- 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!!!
Wow, amazing video! You explained it so well that I finally understood it after breaking my head for sooo many days. Thanks a ton! 🙏🙏
That was the nicest video of this algorithm on YT so far, keep it up
Fantastic video! Best explanation I have seen so far. Would be awesome to see more videos on other algorithms. Thank you!
讲得太好了，非常清晰。Visualization is awesome.
Truly an on "point" explanation. Thank you, keep going!
Clear and precise explanation with a lovely voice.
Simple and to the point. Nicely done.
Quality content, I was looking for. Thank you!
we definitely need more of these explanations from you
Thank you so much, best explanation I’ve come across!
Incredible explanation, the best I have found, thank you very much!!!!!!!!!!!!!!!!!!!!!!!!!
Amazing explanation 🤩🤩 the animation was extremely helpful in seeing how the algorithm works
The only tutorial on the channel had to be the on the topic i was looking for.
This is amazing. Please make more videos on other algorithms!!
amazing amazing amazing and the best explanation for this problem. Thank you
Very visual and clear explanation thank you so much!
the best explanations I've ever seen
This is an amazing explanation! 讲得好棒！
Wow great video! I had a hard time to understand why there was a maximum number of point in the delta region. Thank you
Excellent work and very easy to understand
It's really a clear explaination, amazing !
wow this was amazing. thank you so much for this!!
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.
Beautiful algorithm explained by a beautiful voice
This is so good. Thank you!!
That was awesome
Keep it going🎉🎉
This was perfect.....Thank you so much!
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
so great , that was i am loving version.
Thank you, very nicely explained!
The way you explained is really awesome. Can we expect more videos like this?
no bc
Cleanest explanation ❤️
Fantastic presentation! Thanks a bunch! :)
Amazing thank you for your explanation !!!!
amazing work. helped me a lot
Thank you! Great explanation!
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! Very well explained!
great explanation, thank you
the best explanation ever
Great explanation mam.
how did you find delta in 6,8 do you brute force the left and the right with out divide it ?
Pretty clear. Thank you.
this is such a good and clear explanation, do you mind if I use it for teaching?
Great explanation !
Please make more videos🥲
If possible please create a whole series of your lectures.
Best explanation, bar none
For split pairs why we iterating 1 to 7?
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
God Bless you, you are great
I think it's enough to iterate j from 1 to 4 because in each side the maximum number of points is 4
5:57 Why for j=1 to 7? what's the 7 about?
thanks a lot for your explanation
Thank you! :D
Can you do more videos, please?
Well explained!
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.
3:35 2-delta distance
4:08 2d*d O(1) for each point
best explanation
Thank you!
講的很好！😊
tysm it makes so much more sense now lol
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 🤗🤗
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
thanks. useful.
thank you
Thanks
感恩
Can we expect some more videos?
Great Explanation but i have not understood clearly
الله يدخلش الجنة يارب
Peeps who are here for BUET-18's offline-8 comment here
hey bro 🙂
kere mama mmk
Hola🥲
Yo....bro
hehe
3:55
7 points explanation
W vid
First of all i was on a thought she will definitely waste my time but u nailed it 🔥
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 :)
now find the optimal solution for N-dimensional Euclidean space.
牛逼 上课没听懂在你这里听懂了
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).