Databases
StackOverflow2013
Postsdbo
POTime complexity analysis on Optimal Matrix Search(2D) problem
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POTime complexity analysis on Optimal Matrix Search(2D) problem
    primarykey
    data
    text
    <p>This is going to be a rather large question from me since it requires deep and thorough understanding of the problem and also various approaches taken up to now for the optimal solution.</p> <p>For this matter, I will create a blog later on this as it requires little bit of time from my side to write up the contents and so forth.So, I will provide my blog link once it's ready.</p> <p>Nevertheless, I am posting this so that we can get started discussing.</p> <p>First thing first: </p> <h2>The problem is as follows:</h2> <blockquote> <p>Write an efficient algorithm that searches for a value in an n x m table (two-dimensional >array). This table is sorted along the rows and columns — that is,</p> <p>Table[i][j] ≤ Table[i][j + 1] Table[i][j] ≤ Table[i + 1][j].</p> </blockquote> <p>Here to be noted that each rows and columns are monotonically sorted i.e. each rows and columns are sorted in non-decreasing (lexicographical) order.</p> <p>For the actual problem and a nice discussion on this problem, click on the following link:</p> <p>Note:This post has part 1,2 and 3.</p> <p><a href="http://www.ihas1337code.com/2010/10/searching-2d-sorted-matrix.html" rel="nofollow">Searching 2D Matrix</a></p> <p>Hong Shen, from Griffith University, Australia in December 27, 1995 published the optimal solution for this problem to be O(mlog(2n/m)) for a serial algorithm.</p> <p><a href="http://www.google.com/url?sa=t&amp;source=web&amp;cd=2&amp;ved=0CB0QFjAB&amp;url=http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.116.3096&amp;rep=rep1&amp;type=pdf&amp;rct=j&amp;q=hong%20shen%20optimal%20matrix%20search&amp;ei=h_b9TbifMsLtrAe61rnFDw&amp;usg=AFQjCNEYsY81lKG5Eopg9l0lXGvPSd_Rjg&amp;sig2=vzUsFbeObWvKzNhS09KOkg&amp;cad=rja" rel="nofollow" title="Hong Shen Generalized Optimal Matrix Search">Hong Shen-- Generalized Optimal Matrix Search</a></p> <p>Since then a lots of forum discussions, blogs, and online and offline articles and publications have been made on this, but as of today, as far as I know, O(((log(n))2) is the best claimed on this article with <strong>Improved Binary Search</strong>.</p> <p>Even though the detailed algorithm has not been provided.</p> <p>Now, I have done different variations of solutions on this problem in the hope to bring the optimal solution to be lower than the current best(I think)</p> <p>However, I am not that good at the analysis of time complexities of algorithms.</p> <p>The following is just one of them. As we come up with decisions I will keep providing others and thus come up with the best with all your helps.</p> <p><strong>Here's the first one for you to analyze the time complexity</strong></p> <pre><code> /* NIAZ MOHAMMAD IntPol2d.cpp 1. Find the interpolated mid along column 2. Compare key with each elements in row-wise along the found mid column 3. IF failed DO RECURSIVE call to IntPol2d a. IF(key &gt; a[row][mid]) THEN SET l = mid + 1 and d = row - 1; b. ELSE set r = mid -1 and u = row; */ bool intPol2d(int mat[][6], int M, int N, int target, int l, int u, int r, int d, int &amp;targetRow, int &amp;targetCol,int &amp;count) { count++; if (l &gt; r || u &gt; d) return false; if (target &lt; mat[u][l] || target &gt; mat[d][r]) return false; int mid = l + ((target - mat[u][l])*(r-l))/(mat[d][r]-mat[u][l]); int row = u; while (row &lt;= d &amp;&amp; mat[row][mid] &lt;= target) { if (mat[row][mid] == target) { targetRow = row; targetCol = mid; return true; } row++; } return intPol2d(mat, M, N, target, mid+1, u, r, row-1, targetRow, targetCol,count) || intPol2d(mat, M, N, target, l, row, mid-1, d, targetRow, targetCol,count); } </code></pre> <p><strong>If you require the whole executable code, please let me know</strong>.</p> <p>Thanks for your patience and help and see ya on the discussion board :</p> <p>Note: @ Admins or moderators, let me know if this is not the right place for this type of lengthy question, then I will move to my blog. </p>
    singulars
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PTQuestion
    1. This table or related slice is empty.
    1. USNiaz Mohammad
    plurals
    1. PL
      singulars
      1. LTLinked
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POTime complexity analysis on Optimal Matrix Search(2D) problem
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. POTime complexity analysis on Optimal Matrix Search(2D) problem
      1. This table or related slice is empty.
      1. VTDownMod
    3. VO
      singulars
      1. POTime complexity analysis on Optimal Matrix Search(2D) problem
      1. This table or related slice is empty.
      1. VTUpMod
    1. COWhat does "O(((log(n))2)" mean, and why does it not involve m? What do you think the complexity of your code is? If you can't analyze complexity, what gives you such confidence that you can beat Hong Shen? Why do you pass M and N and never use them?
      singulars
      1. POTime complexity analysis on Optimal Matrix Search(2D) problem
      1. USBeta
    2. CO1. This one is claimed on the link provided "Searching a 2D matrix" and in this case he assumed it to be a square matrix.
      singulars
      1. POTime complexity analysis on Optimal Matrix Search(2D) problem
      1. USNiaz Mohammad
    3. COYou're a beginner? Then you're attempting a problem well beyond your skill (and asking us to do the work). Start with something simpler, like some basic searching and sorting algorithms. Once you master those you'll be better equipped to tackle a problem like this.
      singulars
      1. POTime complexity analysis on Optimal Matrix Search(2D) problem
      1. USBeta
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload