我目前正在测试一些分而治之算法以及它们的常规实现。我对此很陌生,我不确定在使用分治法时是否应该始终获得更好的性能。例如,我已经实现了一种算法,可以按常规方式转置矩阵并使用除以征服,但是使用第一个版本仍然可以获得更好的性能。有可能还是我错过了重要的事情?
这是使用分而治之的代码
void trasponer_DyV(Matriz &matriz)
{
if (matriz.size() >= 2)
{
trasponer_DyV(matriz,matriz.size(),matriz.size());
}
}
void trasponer_DyV(Matriz &matriz,int fil_inicio,int fil_fin,int col_inicio,int col_fin)
{
int tam = fil_fin - fil_inicio;
if (tam == 1)
return;
trasponer_DyV(matriz,fil_inicio,fil_inicio + tam / 2,col_inicio,col_inicio + tam / 2);
trasponer_DyV(matriz,col_inicio + tam / 2,col_inicio + tam);
trasponer_DyV(matriz,fil_inicio + tam,col_inicio + tam);
for (int i = 0; i < tam / 2; i++)
{
for (int j = 0; j < tam / 2; j++)
swap(matriz[fil_inicio + i][col_inicio + tam / 2 + j],matriz[fil_inicio + tam / 2 + i][col_inicio + j]);
}
}
这是蛮力之一:
Matriz trasponer_fuerzabruta(const Matriz &matriz)
{
Matriz ret;
ret.resize(matriz.size());
for (int i = 0; i < matriz.size(); ++i)
{
ret[i].resize(matriz.size());
}
// Todo lo que hacemos es sustituir filas por columnas.
for (int fila = 0; fila < matriz.size(); ++fila)
{
for (int columna = 0; columna < matriz.size(); ++columna)
{
ret[columna][fila] = matriz[fila][columna];
}
}
return ret;
}
谢谢!