心灵火花——好的算法应该是精益求精    1. 把一个具n个元素的数组向左循环移动i个位置的算法设计成具有较好的时间和空间性能。例如abcdefgh向左循环移动3个位置后为defghabc        提示可能三种算法    第一种算法思想: 1步 首先建立一个具有i个元数的临时数组b[i] 2步 将原数组a[n]中的前i个存在临时数组b[i]中 3步 将原数组a[n]中余下的n-I个元往前移i个位置 4步 将临时数组b[i]的元素复制回原数组的后面  算法分析:       该算法使用i个额外的存储空间,使得空间性能降低,也就是以空间换得较小的时间,所以它不是最佳算法   第二种算法思想     1步 首先设计一个函数将数组向左循移动一个位置     2步 调用该算法i 次 算法分析:          该算法由于不开辟临时存储空间,空间性能很好,     但算法的时间性能差,用时间换空间   第三种算法思想      要在有限的资源中解决这个问题似乎很困难,现在 换一个角度看这个问题,把它看作是数组ab转换成 ba ,其中a就代表数组的前i个元素,b代表数中n-i个元 素,这样问题转换成:      a′b→a′b′→(a′b′)′=( b′)′(a′)′=ba 例如把abcdefgh→defghabc 1步  设计一个逆向函数Reversse(intA[ ],int pos,int len) 2步 Reversse(A,0,i-1)→cbadefgh   2步 Reversse(A, i,  n-1);→cbahgfed        3步Reversse(A, 0, n-1);→defghabc 算法分析:       这样处理后时间复杂度和空间复度性能都比较有效,所以当设计算法时要精益求精反复改进它

评论