Блог

Как вычислить временную сложность этой функции шаг за шагом?

Эта функция преобразует список смежности в матрицу, манипулирует матрицей, а затем преобразует матрицу обратно в список

 Graphe *Graphe::grapheInverse( void ){
    
    Graphe *r = new Graphe (_adjacences.size() );
    
    std::vector<vector<int> > matrix(_adjacences.size(), vector<int>( _adjacences.size() ) );
    
    std::vector<vector<int> > liste(matrix.size());

    for (unsigned i = 0; i < _adjacences.size(); i  )
        for (auto j : *_adjacences[i])
            matrix[i][j] = 1;


    for (int i = 0; i < matrix.size(); i  ) { 
        for (int j = 0; j < matrix[i].size(); j  ) {
            if (matrix[i][j] == 1)
                matrix[i][j] = 0;
            else 
                matrix[i][j] = 1;
            if (i == j)
                matrix[i][j] = 0;
        }
    }


    for (int i = 0; i < matrix.size(); i  ){
        for (int j = 0; j < matrix[i].size(); j  ){
            if (matrix[i][j] == 1){
                liste[i].push_back(j);
            }
        }
    }


    for (int i = 0; i < liste.size(); i  ) { 
        for (int j = 0; j < liste[i].size(); j  ) {
            r->ajouterArcs( i, liste[i][j] );        
        }
    }

    return r;
}
  

Обратите внимание, что все следующее относится к временной сложности big-O:

Вычисление временной сложности включает в себя просмотр того, сколько раз вы выполняете итерацию по данным. Один цикл for равен N, поскольку вы касаетесь каждой точки один раз. Вложенный цикл for (для i в данных, для j в данных) равен N ^ 2, потому что вы касаетесь каждой точки один раз для каждой существующей точки.

Цикл for, следующий за циклом for (для i в data выполняется X, для i в data выполняется Y), касается данных N N раз. Это все еще считается временной сложностью N, потому что, поскольку N приближается к очень большому числу, 2N не имеет большого значения. То же самое относится и к вложенным циклам, N ^ 2 N ^ 2 = 2N ^ 2 -> По сути, вы бы проигнорировали любые множители и действовали в зависимости от времени касания N. Это означает, что 2N ^ 2 изменяется на N ^ 2

Повторяю, это специально для большой временной сложности