91影视

Space Complexity for any algorithm defines the total space that is required or used by that algorithm, for different sizes of the input.

To create any variable there required some space for the algorithm to run. All the space that is required by the algorithm is collectively known as the Space Complexity of the algorithm.

In the dynamic programming algorithm for computing the edit distance between strings of length m and n creates a table of size and therefore needs O(mn) time and space. In practice, it will run out of space long before it runs out of time. This space can be reduced by calculating the values of the adjacent cells in the table and the space complexity will be reduced to O(n).

(a)

Consider the Figure 6.4 in the text book, the calculation of a certain cell only needs the values of the upper left, upper and left cells of the cell. Considering the values of the adjacent cells in three directions, the current row and the previous row will be saved.

The state values are enough and they can be stored in a rolling array and the space complexity is O(n).

Therefore, By considering the value of the adjacent square, the edit distance value can be computed in the given space complexity.

(b)

Consider the edit-distance algorithm to calculate the path from the node (0,0) to node (n,m). The optimal path in the dag must pass through an intermediate node $\left(k,\frac{m}{2}\right)$ for some k. In the algorithm swap n and m, which means represents rows and n represents listed rows. The rolling array K with $\frac{n}{2}+1$ columns to store the values of k.

The modified edit-distance algorithm is as follows.

$$\begin{gathered} K(i,0)=i \\ ifj>\frac{n}{2} \\ ifE(i,j)=E\left(i-1,j\right)+1 \\ K\left(i,j-\frac{n}{2}\right)=K\left(i-1,j-\frac{n}{2}\right) \\ elseifE(i,j)=E(i,j-1)+1 \\ K\left(i,j-\frac{n}{2}\right)=K\left(i-1,j-\frac{n}{2}-1\right) \\ ElseifE(i,j)=E(i-1,j-1)+diff(i,j) \\ K\left(i,j-\frac{n}{2}\right)=K\left(i-1,j-\frac{n}{2}-1\right) \end{gathered}$$

(c)

Consider that the given scheme is the recurrence relation, the time complexity is as follows,

$\begin{array}{rcl}T(m,n)& =& O\left(mn\right)+\frac{1}{2}O\left(mn\right)+\frac{1}{4}O\left(mn\right)+\frac{1}{8}O\left(mn\right)...\\ & =& O\left(mn\right)\end{array}$

The time complexity is still O(mn), the constant is due to that the size of the algorithm is doubles and the difficulty of the algorithm implementation has also been greatly improved.

Therefore, it has been shown that the given scheme can be made to run in O(mn) time and O(n) space.