2. 考研
  3. 假设输入，一句英语句子：“I am a student”，要求输出“student．a am I”。也就是说以单词为基本单位将句子中的所有单词翻转过来。请实现一个时间和空间上尽可能高效率的算法，将句子中所有的单词翻转过来。要求： 说明你所设计算法的时间复

假设输入，一句英语句子：“I am a student”，要求输出“student．a am I”。也就是说以单词为基本单位将句子中的所有单词翻转过来。请实现一个时间和空间上尽可能高效率的算法，将句子中所有的单词翻转过来。要求： 说明你所设计算法的时间复

admin2014-04-17  59
问题 假设输入，一句英语句子：“I am a student”，要求输出“student．a am I”。也就是说以单词为基本单位将句子中的所有单词翻转过来。请实现一个时间和空间上尽可能高效率的算法，将句子中所有的单词翻转过来。要求：
说明你所设计算法的时间复杂度和空间复杂度。
选项
答案空间复杂度分析，在这个过程中，除去字符串本身外：额外的空间消耗为O(1)=时间复杂度分析：在这个算法中，通过Reverse函数翻转一个字符串的复杂度为O(n)。假设每个单词的长度分别为wi，那么有∑wi≤n。在这个算法中，先翻转了整个字符串，时间复杂度为O(n)，然后翻转每个单词的时间复杂度为O(wi)，整个算法的时间复杂度为O(n+∑wi)=O(n)。
解析
转载请注明原文地址:https://kaotiyun.com/show/vixi777K
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

相关试题推荐
随机试题
最新回复(0)