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

admin2014-04-17 76

问题假设输入，一句英语句子：“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题库学硕统考专业分类

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

计算机408

学硕统考专业

明万历年间使地主与农民之间仅仅存在着单纯的经济关系而没有人身依附关系的是()。

对资本主义萌芽出现起决定性作用的明朝农业生产特点是()。

俄罗斯的私有化进程始于()年。

外国侵略者通过不平等条约取得的特权中，按时间先后顺序排列应是()。①外国商船和军舰可以在长江各口岸自由航行②外国人可以在通商口岸开设工厂③可在通商口岸建立教堂④领事裁判权和片面最惠国待遇

汉灵帝中平元年(184)，()在7州28郡同时俱起，这是中国历史上第一次组织、准备比较严密的农民起义。

以下关于玛雅天文学成就的叙述，正确的是()。①玛雅人创造的“玛雅历”是一种太阳历。②玛雅人的历法，与宗教祭祀有着密切联系。③奇钦.伊查天文观象台是玛雅天文学的伟大成就。④玛雅人的历法中，采用了12进位法。

简述西欧城市兴起的原因、方式及其影响。

()是一部上起传说中的黄帝，下迄汉武帝时期的中国通史，是中国历史上第一部内容完整、结构周密的历史著作。

相对于微程序控制器，硬布线控制器的特点是()。

IEEE754标准浮点数的尾数采用()机器数形式。

ThenorthernpartsoftheUnitedStatesgetverycoldinthewinter.Itsnowsagreatdealandthetemperatureoftengoes【C1】___

妇女分娩时死亡，尸体解剖发现肺小动脉内有角化上皮细胞、毛发等物质，其死亡原因可能是()

简述法律继承的内容。

下列选项中，不属于现金流出的是()。

建设工程监理合同属于()。

我国《宪法》规定：“父母有抚养教育未成年子女，成年子女有赡养抚助父母的义务。”这说明()。

以()为基础的数据库系统称为关系数据库系统。

Sincethedawnofe-mail,usingsarcasmindigitalcommunicationhascreatedstrifeandconfusionbetweenfriends,colleaguesan

I’vedecidedtotaketheplungeandstartupmyownbusiness.Theunderlinedwordmeans