我目前正在测试一些分治算法和它们的常规实现。我对此还比较新,不确定在使用分治时是否总是能得到更好的性能表现。例如,我已经实现了一个算法来传统地转置矩阵并使用分治方法,但我仍然使用第一版获得了更好的性能。这可能是可能的,或者我漏掉了一些重要的东西吗?
这里是使用分治的代码:
void trasponer_DyV(Matriz &matriz)
{
if (matriz.size() >= 2)
{
trasponer_DyV(matriz, 0, matriz.size(), 0, 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, fil_inicio, fil_inicio + tam / 2, col_inicio + tam / 2, col_inicio + tam);
trasponer_DyV(matriz, fil_inicio + tam / 2, fil_inicio + tam, col_inicio, col_inicio + tam / 2);
trasponer_DyV(matriz, fil_inicio + tam / 2, fil_inicio + tam, col_inicio + tam / 2, 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;
}
提前感谢!