5
\$\begingroup\$

* Time complexity: O(N)
* Memory complexity: \$O(1)\$

Is my calculation of complexity correct for this code?

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

using Vector = vector<vector<int>>;

int main()
{
    const size_t SIZE = 7;

    Vector image(SIZE, vector<int>(SIZE));

    cout << "******* original image ******" << endl;
    int value = 0;
    for (auto& i : image)
    {
        for (auto& j : i)
        {
            cout << (j = value) << ' ';
        }

        value++;
        cout << '\n';
    }

    // rotate image 90 degree clockwise O(N)time & O(1)memory ???
    for (size_t i = 0; i < image.size(); ++i)
    {
        for (size_t j = 0; j < (image.size() - i); ++j)
        {
            swap(image[i][j], image[image.size() - j - 1][image.size() - i - 1]);
        }
    }

    cout << "\n******* rotated image ******" << endl;
    for (const auto& i : image)
    {
        for (const auto& j : i)
        {
            cout << j << ' ';
        }

        cout << '\n';
    }
}
\$\endgroup\$
3
\$\begingroup\$
using namespace std;

Try to avoid importing namespaces like this, as it makes the code less readable and harder to maintain. More details at Why is using namespace std bad practice?

        swap(image[i][j], image[image.size() - j - 1][image.size() - i - 1]);

Case in point. When I first read this line, I started looking for a function called swap in your code. Of course, there isn't one. But if I look for std::swap, I can find it easily. One of the advantages of namespaces is that they make it simple to tell the source of a piece of code. If you had written out the name, it would have been trivial for me to tell that this was using std::swap.

using Vector = vector<vector<int>>;

I would pick another name for this. Making Vector and vector mean different things is confusing. Also, a vector is a name for something one dimensional. The two dimensional name would be Matrix. However, in this case, if all you want to optimize is rotation, you can do better.

Instead of just using a vector of vectors, make a new class, e.g. Image or Rotatable_Image.

class Rotatable_Image {
  private static const int ROTATIONS_IN_CIRCLE = 4;

  private std::vector<std::vector<int>> matrix;
  private int rotation_count = 0;

  public Rotatable_Image(size_t size) {
    matrix.resize(size, std::vector<int>(size);
  }

  // rotates image 90 degrees clockwise
  public void rotate() {
    ++rotation_count;

    while ( rotation_count > ROTATIONS_IN_CIRCLE ) {
      rotation_count -= ROTATIONS_IN_CIRCLE;
    }
  }

  public int & get_pixel(int row, int column) {
    switch ( rotation_count % ROTATIONS_IN_CIRCLE ) {
      case 0:
        return matrix[row][column];
      case 1:
        return matrix[matrix.size() - column - 1][row];
      case 2:
        return matrix[matrix.size() - row - 1][matrix.size() - column - 1];
      case 3:
        return matrix[column][matrix.size() - row - 1];
    }
  }

  public size_t size() {
    return matrix.size();
  }
};

This class tracks the number of times that the image has been rotated 90 degrees clockwise. It uses that to determine which pixel to return when passed a row and a column.

With this, memory complexity of rotating is \$O(1)\$ if you are talking purely about the memory increase. Note that the program as a whole is \$O(n^2)\$, because you are creating an \$n\$ by \$n\$ object. Rotation's time complexity is \$O(1)\$ and reading an element is \$O(1)\$. That said, if you are going to read this repeatedly, you may be better off performing the swap. You won't improve your complexity analysis, but you might improve performance.

You lose the ability to iterate over the rows and columns separately, but otherwise this remains similar in initialization and use.

int main()
{
    const size_t SIZE = 7;

    Rotatable_Image image(SIZE);

    cout << "******* original image ******" << endl;
    int value = 0;
    for (size_t i = 0; i < image.size(); ++i)
    {
        for (size_t j = 0; j < image.size(); ++j)
        {
            cout << (get_pixel(i, j) = value) << ' ';
        }

        value++;
        cout << '\n';
    }

    // rotate image 90 degree clockwise O(1)time & O(1)memory
    image.rotate();

    cout << "\n******* rotated image ******" << endl;
    for (size_t i = 0; i < image.size(); ++i)
    {
        for (size_t j = 0; j < image.size(); ++j)
        {
            cout << get_pixel(i, j) << ' ';
        }

        cout << '\n';
    }
}

As solutions go, this seems more of a curiosity than anything else. Unless you are rotating as often as you are reading, which seems an unlikely usage, this will probably be slower. And it certainly doesn't allow you to manipulate the image as effectively in any other way than rotating. But, if you want to do better than \$O(n^2)\$, you will have to do something to make it so that you don't swap memory around.

Note: I haven't tried to run this. Apologies if I flubbed something that testing would have caught.

\$\endgroup\$
  • 1
    \$\begingroup\$ fabulous .. i tested it here link ideone.com/MZtzxJ. its really great \$\endgroup\$ – MORTAL Dec 19 '14 at 8:13
5
\$\begingroup\$

This code doesn't rotate the image 90 degrees clockwise.

We can see this by making each entry in the matrix distinct (the important part is moving value++ inside the inner loop)

for (auto& i : image)
{
    for (auto& j : i)
    {
        cout << setfill(' ') << setw(3) << (j = value) << ' ';
        value++;
    }

    cout << '\n';
}

Then the output is

$ ./a.exe
******* original image ******
  0   1   2   3   4   5   6
  7   8   9  10  11  12  13
 14  15  16  17  18  19  20
 21  22  23  24  25  26  27
 28  29  30  31  32  33  34
 35  36  37  38  39  40  41
 42  43  44  45  46  47  48

******* rotated image ******
 48  41  34  27  20  13   6
 47  40  33  26  19  12   5
 46  39  32  25  18  11   4
 45  38  31  24  17  10   3
 44  37  30  23  16   9   2
 43  36  29  22  15   8   1
 42  35  28  21  14   7   0
\$\endgroup\$
  • 1
    \$\begingroup\$ good point add this reverse(image.begin(), image.end()); \$\endgroup\$ – MORTAL Dec 18 '14 at 3:51
5
\$\begingroup\$

Time complexity is not \$O(N)\$. It is \$O(N^2)\$.

When i = 0, the number of swaps is N.
When i = 1, the number of swaps is N-1.

...

when i = N-1, the number of swaps is 1.

Total number of swaps is \$1 + 2 + ... + N-1 + N = N*(N+1)/2\$

Use the following updated code to verify the number of swaps.

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

using Vector = vector<vector<int>>;

int main()
{
    const size_t SIZE = 14;

    Vector image(SIZE, vector<int>(SIZE));

    cout << "******* original image ******" << endl;
    int value = 0;
    for (auto& i : image)
    {
        for (auto& j : i)
        {
            cout << (j = value) << ' ';
            value++;
        }

        cout << '\n';
    }

    // rotate image 90 degree clockwise O(N)time & O(1)memory ???
    size_t numTotalSwaps = 0;
    for (size_t i = 0; i < image.size(); ++i)
    {
       size_t numSwaps = 0;
        for (size_t j = 0; j < (image.size() - i); ++j)
        {
            swap(image[i][j], image[image.size() - j - 1][image.size() - i - 1]);
            ++numTotalSwaps;
            ++numSwaps;
        }
        cout << "\nNumber of swaps  for i = " << i << ": " << numSwaps << endl;
    }

    cout << "\nNumber of total swaps: " << numTotalSwaps << endl;
    cout << "\n******* rotated image ******" << endl;
    for (const auto& i : image)
    {
        for (const auto& j : i)
        {
            cout << j << ' ';
        }

        cout << '\n';
    }
}
\$\endgroup\$
  • 1
    \$\begingroup\$ thanks .. that means whenever you have loop, it is always N*N \$\endgroup\$ – MORTAL Dec 18 '14 at 5:02
  • 2
    \$\begingroup\$ @MORTAL, that is correct whenever you have two loops to iterate over a 2D array. \$\endgroup\$ – R Sahu Dec 18 '14 at 5:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.