Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p><strong>Your pseudocode gives an algorithm in O(2^n). I think you can have something in O(n^3).</strong></p> <hr> <p>First of all, let's see the complexity of your algorithm. Let's say that the number of operations needed to check the parenthesization is <code>T(n)</code>. If I understood well, your algorithm consists of : </p> <ul> <li><p>Cut the expression in two (n-1 possibilities)</p></li> <li><p>Check if the left and the right part have appropriate parenthesization.</p></li> </ul> <p>So <code>T(n)</code> = <code>checking if you cut at the first place</code> + <code>checking if you cut at the second place</code> + ... + <code>checking if you cut at the last place</code></p> <p><code>T(n)</code> = <code>T(1)+T(n-1)</code> + <code>T(2)+T(n-2)</code> + ... + <code>T(n-1)+T(1)</code> + n</p> <p>A bit of computation will tell you that <code>T(n) = 2^n*T(1) + O(n^2) = O(2^n)</code></p> <hr> <p>My idea is that what you only need is to check for parenthesization are the "subwords". The "subword_i_j" consists of all the litterals between position i and position j. Of course <code>i&lt;j</code> so you have <code>N*(N-1)/2</code> subwords. Let's say that <code>L[i][j]</code> is the number of valid parenthesizations of the subword_i_j. For the sake of convenience, I'll forget the other values <code>M[i][j]</code> that states the number of parenthesization that leads to false, but don't forget that it's here!</p> <p>You want to compute all the possible subwords starting from the smallest ones (size 1) to the biggest one (size N).</p> <p>You begin by computing <code>L[i][i]</code> for all i. There are N such values. It's easy, if the i-th litteral is True then <code>L[i][i]=1</code> else <code>L[i][i]=0</code>. Now, you know the number of parenthesization for all subwords of size 1.</p> <p>Lets say that you know the parenthesization for all subwords of size S.</p> <p>Then compute <code>L[i][i+S]</code> for i between 1 and N-S. These are subwords of size S+1. It consists of splitting the subword in all possible ways (S ways), <strong>and</strong> checking if the left part(which is a subword of size S1&lt;=S) <strong>and</strong> the right part(which is of size S2&lt;=S) <strong>and</strong> the operator inbetween (or, xor, and) are compatible. There are S*(N-S) such values. </p> <p>Finally, you'll end up with <code>L[1][N]</code> which will tell you if there is a valid parenthesization.</p> <p>The cost is : </p> <p><code>checking subwords of size 1</code> + <code>checking subwords of size 2</code> + ... + <code>checking subwords of size N</code></p> <p>= <code>N</code> + <code>N-1</code> + <code>2*(N-2)</code> + <code>2*(N-2)</code> + .. + <code>(N-1)*(1)</code></p> <p>= <code>O(N^3)</code></p> <hr> <p>The reason the complexity is better is that in your pseudocode, you check multiple times the same subwords without storing the result in memory.</p> <p>Edit : Arglllll, I overlooked the sentence <code>we save all the solutions to subproblems and read them when we meet them again. thus save time.</code>. Well, seems that if you do, you also have an algorithm in worst-case O(N^3). Don't think you can do much better than that...</p>
    singulars
    1. This table or related slice is empty.
    1. POcounting boolean parenthesizations implementation
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USFezvez
    1. USFezvez
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. This table or related slice is empty.
 

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