求教大神一个关于时间复杂度的有关问题
求教大神一个关于时间复杂度的问题
小弟最近正在上算法课
老是留了一作业 给了一本单词表的文档（里面只有单词本身） 然后读取里面的内容 找出最长的单词 单词平均长度什么的
但部分都解决了 但是还有一个问题没有解决
给出下面一个方法 判断该单词是否为字典顺序：
bool alpha(string s){
int ln = s.size();
for (int i = 0; i < ln - 1; ++i){
if (s[i] > s[i+1]){
return false;
}
}
return true;
}
然后 考虑平均每个单词的比较次数 并给出时间复杂度 并举例最坏的情况。
最坏的情况肯定是这个单词是按字典顺序的 比如单词ABC 就得O（N^2）最好的情况是每个就比较了第一个和第二个字母 然后就发现不是字母顺序直接返回一个FALSE
那么平均的次数怎么求呢？ 而且这个方法的时间复杂度是O(N^2)吗？
我刚学不太懂 求指教！
------解决方案--------------------
该算法的复杂度为O(n)，平均每个单词的比较次数与文本中单词长度的分布规律有关，不知道有没有更好的算法是否可以使复杂度降低到O(lgn)
------解决方案--------------------
每个单词只有一次循环啊，当然是O(n)
------解决方案--------------------
可以考虑给程序中添加一个计数器变量，根据计数器推算出每个单词的平均比较次数
------解决方案--------------------
给出时间复杂度的同时必须给出其中变量的含义。你先要确定n代表单词长度还是单词数量。如果用两个变量m,n分别表示的话，时间复杂度是O(mn），不能写成O(n^2)。
只针对一个单词的话，n=1，时间复杂度是O(m)。针对大量单词的话，如果忽略m的变化，时间复杂度O（n)。
小弟最近正在上算法课
老是留了一作业 给了一本单词表的文档（里面只有单词本身） 然后读取里面的内容 找出最长的单词 单词平均长度什么的
但部分都解决了 但是还有一个问题没有解决
给出下面一个方法 判断该单词是否为字典顺序：
bool alpha(string s){
int ln = s.size();
for (int i = 0; i < ln - 1; ++i){
if (s[i] > s[i+1]){
return false;
}
}
return true;
}
然后 考虑平均每个单词的比较次数 并给出时间复杂度 并举例最坏的情况。
最坏的情况肯定是这个单词是按字典顺序的 比如单词ABC 就得O（N^2）最好的情况是每个就比较了第一个和第二个字母 然后就发现不是字母顺序直接返回一个FALSE
那么平均的次数怎么求呢？ 而且这个方法的时间复杂度是O(N^2)吗？
我刚学不太懂 求指教！
算法
算法
时间复杂度
字典顺序
------解决方案--------------------
该算法的复杂度为O(n)，平均每个单词的比较次数与文本中单词长度的分布规律有关，不知道有没有更好的算法是否可以使复杂度降低到O(lgn)
------解决方案--------------------
每个单词只有一次循环啊，当然是O(n)
------解决方案--------------------
可以考虑给程序中添加一个计数器变量，根据计数器推算出每个单词的平均比较次数
------解决方案--------------------
给出时间复杂度的同时必须给出其中变量的含义。你先要确定n代表单词长度还是单词数量。如果用两个变量m,n分别表示的话，时间复杂度是O(mn），不能写成O(n^2)。
只针对一个单词的话，n=1，时间复杂度是O(m)。针对大量单词的话，如果忽略m的变化，时间复杂度O（n)。