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.
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 ^_^
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
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.
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
Should the space complexity not be O(n)? Explaination below. It's true that for each call with make take O(n) space which is the n for that call. And the depth is log n. However, in each next call N is also half. So it's like N + N/2 + N/4 .... 1, which is 2n, so O(n) When we are in a recusrive call, we shouldn't consider space from calls that have finished. And for a given call only it's previous sizes are active. It's similar to how in merge sort (with using extra auxilary array to merge), the space complexity would still be O(n).
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).
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!!!
That was the nicest video of this algorithm on YT so far, keep it up
Truly an on "point" explanation. Thank you, keep going!
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.
The way you explained is really awesome. Can we expect more videos like this?
no bc
this is amazing. Thank you so much for saving our souls in algorithm class.
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
Clear and precise explanation with a lovely voice.
5:57 Why for j=1 to 7? what's the 7 about?
The only tutorial on the channel had to be the on the topic i was looking for.
Thank you after 3 years
讲得太好了，非常清晰。Visualization is awesome.
Wow, amazing video! You explained it so well that I finally understood it after breaking my head for sooo many days. Thanks a ton! 🙏🙏
Thank you so much. Couldn't be more clear
This is such a great explanation! Thank you so much.
we definitely need more of these explanations from you
Incredible explanation, the best I have found, thank you very much!!!!!!!!!!!!!!!!!!!!!!!!!
Fantastic video! Best explanation I have seen so far. Would be awesome to see more videos on other algorithms. Thank you!
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
An excellent explanation of the problem
the best explanations I've ever seen
3:35 2-delta distance
4:08 2d*d O(1) for each point
your video is very very great! I love it. Thank you very much!
Quality content, I was looking for. Thank you!
For split pairs why we iterating 1 to 7?
Wow great video! I had a hard time to understand why there was a maximum number of point in the delta region. Thank you
Simple and to the point. Nicely done.
amazing amazing amazing and the best explanation for this problem. Thank you
Thank you so much, best explanation I’ve come across!
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.
4:40 bookmark
so great , that was i am loving version.
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 🤗🤗
very very nice explanantion....
This is so good. Thank you!!
This is amazing. Please make more videos on other algorithms!!
Great one, especially the 2δ X δ part!!
hello, i wish you could do more explanation videos like this. I really appreciate your clear explanation!!!
Beautiful algorithm explained by a beautiful voice
Fantastic presentation! Thanks a bunch! :)
Ommggg amazing explaination
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
wow this was amazing. thank you so much for this!!
that was a great explanation, thank you
Very visual and clear explanation thank you so much!
This was perfect.....Thank you so much!
Excellent work and very easy to understand
God Bless you, you are great
Thank you! Great explanation!
That was awesome
Keep it going🎉🎉
This is an amazing explanation! 讲得好棒！
Thank you, very nicely explained!
the best explanation ever
Best explanation, bar none
Great explanation mam.
It's really a clear explaination, amazing !
Pretty clear. Thank you.
Amazing explanation 🤩🤩 the animation was extremely helpful in seeing how the algorithm works
I think it's enough to iterate j from 1 to 4 because in each side the maximum number of points is 4
how did she arrived at the 2nd strip
this is such a good and clear explanation, do you mind if I use it for teaching?
great explanation, thank you
Thank you so much ❤❤
Great explanation !
Amazing thank you for your explanation !!!!
Cleanest explanation ❤️
Thank You ma'am.
amazing work. helped me a lot
thank you! Very well explained!
how did you find delta in 6,8 do you brute force the left and the right with out divide it ?
講的很好！😊
Please make more videos🥲
If possible please create a whole series of your lectures.
Can you do more videos, please?
thanks a lot for your explanation
Thank you! :D
Thank you!
Should the space complexity not be O(n)?
Explaination below. It's true that for each call with make take O(n) space which is the n for that call. And the depth is log n.
However, in each next call N is also half.
So it's like N + N/2 + N/4 .... 1, which is 2n, so O(n)
When we are in a recusrive call, we shouldn't consider space from calls that have finished.
And for a given call only it's previous sizes are active.
It's similar to how in merge sort (with using extra auxilary array to merge), the space complexity would still be O(n).
Can we expect some more videos?
Well explained!
best explanation
3:55
7 points explanation
tysm it makes so much more sense now lol
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 :)
thank you
thanks. useful.
Peeps who are here for BUET-18's offline-8 comment here
hey bro 🙂
kere mama mmk
Hola🥲
Yo....bro
hehe
wonder how this video ' made
Thanks
الله يدخلش الجنة يارب
感恩
Great Explanation but i have not understood clearly
First of all i was on a thought she will definitely waste my time but u nailed it 🔥
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).
W vid
now find the optimal solution for N-dimensional Euclidean space.
牛逼 上课没听懂在你这里听懂了