probably you are mistaken about the complexity calculations,
the above algo will search for the first element in the 2D matrix,
and if you look carefully , at max n-1 match for each unsuccessful 1D
combination is done
hence complexity goes to n(n-1) or O(n^2) at max with space complexity
O(n).
BTW, I did not get your idea of reducing complexity , can you describe
it in detail ?
On Nov 4, 8:41 am, surender sanke <surend...@gmail.com> wrote:
> @vikas
>
> ur algo will search for 1st element of 1d in whole 2d array,
> on worst case u'll search it in n^2, then search for all 1d elements
> in 2d in O(n)
> so whole complexity goes to O(n^2 +n)
> it can be reduced if we use hashing of 1d array, and count_found
> and while searching for 1st element of 1d in 2d array, if it's found
> make temp[i][j] as true(even though its not first element) and false
> if its not in 1d hash, and increase count_found
> this will reduce to O(n^2)
>
> surender
>
> On 11/1/11, vikas <vikas.rastogi2...@gmail.com> wrote:
>
> > ok,
> > so do it like this;
> > 1. create boolean array
> > boolean temp[][] = new boolean[row][column];
> > init(temp, true);
>
> > 2. traverse the array for the 1d array of 0th index and then a
> > recursive search
> > if search fails, or position already contains false, return and search
> > again
>
> > boolean search(int searchArray[][], int givenArray[], int rpos, int
> > cpos, int gpos){
> > if(gpos > givenArray.len) return false;
> > if(temp[rpos][cpos] == false) return false;
> > if(searchArray[rpos][cpos] == givenArray[gpos])
> > {
> > temp[rpos][cpos] = search(searchArray, givenArray, rpos
> > +1, cpos, gpos+1)|
> > search(searchArray,
> > givenArray, rpos-1, cpos, gpos+1) |
> > search(searchArray,
> > givenArray, rpos, cpos+1, gpos+1)|
> > search(searchArray,
> > givenArray, rpos+1, cpos-1, gpos+1)
> > }
> > if(temp[rpos][cpos]) return true;
> > if(cpos < searchArray.len)
> > search(searchArray, givenArray, rpos, cpos+1, 0);
> > else
> > search(searchArray, givenArray, rpos+1, 0, 0);
>
> > }
>
> > On Nov 1, 4:25 pm, SAMM <somnath.nit...@gmail.com> wrote:
> >> For example :-
>
> >> 2d array ::
>
> >> 1 2 3 4 5 6
> >> 7 8 9 10 11 12
> >> 13 14 15 16 17 18
> >> 19 20 21 22 23 24
>
> >> we hav 1d array as :-- 13 2 21 10 23 12
>
> >> So the 1d array is a subset of 2d array ...
>
> >> On 11/1/11, vikas <vikas.rastogi2...@gmail.com> wrote:
>
> >> > what do you mean by subset of 1D present in the 2D array? is it
> >> > something like 3245 , the search may be 3245/ 24/ 45/ .... all 16
> >> > subsets need to be searched?
>
> >> > On Oct 28, 12:02 pm, SAMMM <somnath.nit...@gmail.com> wrote:
> >> >> How do u plan to implement it ???
>
> >> > --
> >> > You received this message because you are subscribed to the Google
> >> > Groups
> >> > "Algorithm Geeks" group.
> >> > To post to this group, send email to algogeeks@googlegroups.com.
> >> > To unsubscribe from this group, send email to
> >> > algogeeks+unsubscr...@googlegroups.com.
> >> > For more options, visit this group at
> >> >http://groups.google.com/group/algogeeks?hl=en.
>
> >> --
> >> Somnath Singh
>
> > --
> > You received this message because you are subscribed to the Google Groups
> > "Algorithm Geeks" group.
> > To post to this group, send email to algogeeks@googlegroups.com.
> > To unsubscribe from this group, send email to
> > algogeeks+unsubscr...@googlegroups.com.
> > For more options, visit this group at
> >http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
