Is it possible to avoid this algorithm O (n ^ 4)?

Question

DISCLAIMER: This is not a matter of homework. I don’t even go to school.

#include <stdio.h> void printIntersect(float, float, float, float); int main(){ int x, y, z, a; float slopes[] = {5, 9, 4/3.0f, 2/3.0f, 3}; float inter[] = {3, 2, 1, 0, 5/3.0f}; for(x = 0; x < (sizeof(slopes) / sizeof(slopes[0])) - 1; x++) for(y = 1; y < (sizeof(slopes) / sizeof(slopes[0])); y++) for(z = 0; z < sizeof(inter) / sizeof(inter[0]); z++) for(a = 0; a < sizeof(inter) / sizeof(inter[0]); a++) if(slopes[x] != slopes[y]) printIntersect(slopes[x], slopes[y], inter[z], inter[a]); return 0; } void printIntersect(float m_one, float m_two, float b_one, float b_two){ float m_final, b_final, x_intersect; m_final = m_one - m_two; b_final = b_two - b_one; if(m_final < 0 && b_final < 0) m_final *= -1.0f, b_final *= -1.0f; if (b_final != 0) x_intersect = b_final / m_final; else x_intersect = 0; printf("The intersection of y = %.2fx %c %.2f and y = %.2fx %c %.2f is x = %.2f\n", m_one, (b_one < 0) ? '-' : '+', b_one, m_two, (b_two < 0) ? '-' : '+', b_two, x_intersect); return; } 

Scenario: One of my C books had an exercise that I’m not sure about. I realized that I should have two arrays: one of the possible slopes of the line, the other - all possible intercepts. The goal was to use all possible combinations of slopes and intercepts with two lines to find their intersection. I had to ignore parallel lines and duplicate lines (which are implicitly ignored anyway, if they cannot be parallel, then there is no way that they could be the same line).

Assuming the premise (and I really don't care, it's just an exercise), the program I wrote uses 4 nested loops. You can understand why this concerns me, but again, maybe 4 of them are necessary.

Since I cannot have parallel lines, I repeat the slopes starting from the first line, and then iterate over all the other slopes of the array as the second slope of the line. Thus, I get all possible combinations of slopes.

Interceptions are different, because I can have lines with the same interceptions, and they will still be different. Thus, the iteration between them does not require duplicates. At the same time, as I repeat the array of interceptions, every possible pair in these two lines should be taken into account.

If the lines are not parallel, I call a function that will print an intercept x.

My question is, can this be avoided, or at least simplified this solution to O (n ^ 4)? Do you have any tips on handling such arrays?

Answer 1

Given a slope a and b , you can make strings a*b . There are a*b choose 2 pairs of a*b choose 2 lines. This is about half that a*b*a*b (this is ( a*b*(a*b-1)/2 ). Without additional information, it seems like you should check all of them - so your ego is really O(a*a*b*b) .

EDIT: Let's look at the question in different ways from the point of view of the answer. Given a slopes and b intersect, and making lines a*b , combining them, how many intersections will we have? For simplicity, suppose that the set of slopes is different.

This is a different question than the question of how many intersections we gave to lines n , due to how the lines are constructed. Given one slope, we create parallel lines b . Given the following, we create other parallel lines b , none of which are parallel to the first set of lines. Repeat a time.

In one set, we have no intersections, since they are all parallel.

Between the two sets, how many intersections do we have? None of the lines in one set is parallel to the lines in the other set, so each line in one set will intersect once with each line of the second set. Since each set has lines b , b*b will intersect between any two sets.

Here we notice that all these sets of lines also have the same set b . So, for each additional set of lines that you intersect with the current set of intersecting lines, you will add intersections (b*b - b)*c = b*c*(b-1) , where c is the number of sets of lines that are already are included because the intersections in b y-intercepts have already been taken into account, therefore we add only b*(b - 1) tags for each row set.

So, we have an initial b^2 for two sets plus b*(b - 1)*2 for adding a third, plus b*(b - 1)*3 for adding a fourth, etc. to b*(b-1)*(a-1) to add the set a th. That is, the number of intersections I is equal to:

 I = b^2 + 2b(b-1) + 3b(b-1) + ... + (a-1)b(b-1) 

We can rewrite b^2 as b + b(b-1) :

 I = b + b(b-1) + 2b(b-1) + ... + (a-1)b(b-1) 

Change the total b(b-1) in the last a-1 conditions:

 I = b + b(b-1)[1 + 2 + ... + (a-1)] 

Note that the sum of numbers from 1 to x is x*(x+1)/2 :

  (a-1)*a I = b + b(b-1) ------- 2 a*(a-1)*b*(b-1) = b + --------------- 2 (a^2 - a)(b^2 - b) = b + ------------------ 2 a^2*b^2 - a^2*b - a*b^2 + a*b + 2b = ---------------------------------- 2 

Thus, any algorithm that you use, you will have to generate many separate parts of the output, which is really less than a^2*b^2 , but not a significant amount.

Answer 2

Well, we can already halve the cycle by changing the starting index of the second cycle.

 for (y = 1, ...) 

to

 for (y = x + 1; ...) 

gives

 for (x = 0; x < (sizeof(slopes) / sizeof(slopes[0])) - 1; x++) for (y = x + 1; y < (sizeof(slopes) / sizeof(slopes[0])); y++) for (z = 0; z < sizeof(inter) / sizeof(inter[0]); z++) for (a = 0; a < sizeof(inter) / sizeof(inter[0]); a++) printIntersect(slopes[x], slopes[y], inter[z], inter[a]); 

I also removed the equality check, although as indicated in jxh, slopes may contain duplicate entries. Well, I did this because you can remove duplicates in O (n).

Of course, this does not alter the overall time complexity of the algorithm, but it should help with runtime.

Answer 3

I do not believe that you can get away from O (M ² x Y ² ) (M different slopes and Y different intercepts), but you can filter so that they differ from each other in the first place. This allows your program to work faster if the input contains many duplicates. In addition, without removing duplicate y-intercepts, you can also generate and print duplicate line intersections.

So, using qsort , you can sort the input and then remove duplicates. Since sorting is O (N x log ₂ N), this does not affect the overall complexity of your algorithm (and speeds it up when there are many duplicates). Using a hash table, you can delete duplicates faster, but the standard C library does not provide it (you must find it or implement it yourself).

 #define ARRAY_SZ(x) (sizeof(x)/((void *)x == &x ? sizeof(x[0]) : 0)) static int is_equal_float (float a, float b) { /*...*/ } static int cmp_float (const void *a, const void *b) { float af = *(const float *)a; float bf = *(const float *)b; if (is_equal_float(af, bf)) return 0; return (af > bf) - (af < bf); } /* ... */ qsort(slopes, ARRAY_SZ(slopes), sizeof(slopes[0]), cmp_float); qsort(inter, ARRAY_SZ(inter), sizeof(slopes[0]), cmp_float); for (x = 0, y = 1; y < ARRAY_SZ(slopes) - 1; y++) if (slopes[y] != slopes[x]) slopes[++x] slopes[y]; for (z = 0, a = 1; a < ARRAY_SZ(inter) - 1; a++) if (inter[z] != inter[a]) inter[++z] slopes[a]; M = x+1; Y = z+1; for (x = 0; x < M - 1; x++) for (y = x + 1; y < M; y++) for (z = 0; z < Y; z++) for (a = 0; a < Y; a++) printIntersect(slopes[x], slopes[y], inter[z], inter[a]); 

I am obscuring how to compare float s, but you can consult The most efficient way for float and double compare to answer the question of how to do this which fits your application requirements.