从算法题看复杂度

从算法题看复杂度轮转数组三种思路1、直接法2、新数组法3、原地法轮转数组题目三种思路1、直接法保存最后一个数据前面数据挨个前移。循环k次。最后把end放到开头while(k--){intendnums[numssize-1];for(intinumssize-1;i0;i--){nums[i]nums[i-1];}nums[0]end;}然而回顾复杂度算法时间复杂度外层循环k次内层循环i次。两个未知数相乘。O(n^2)空间复杂度创建了常数个变量。O(1)2、新数组法申请新数组空间先将后k个数据放到新数组中再将剩下的数据挪到新数组防止ik越界要模上numssizeintnewarr[100000]{0};for(inti0;inumssize;i){newarr[(ik)%numssize]nums[i];}for(inti0;inumssize;i){nums[i]newarr[i];}此时的时间复杂度O(n)空间复杂度O(n)。时间换空间。3、原地法前n-k个逆置——后k个逆置——整体逆置此时的空间复杂度降到O(1)时间复杂度不变。但方法很有数学味道比较难想。