时间复杂度相关有关问题
时间复杂度相关问题
在分析时间复杂度时，怎样找基本操作？基本操作可以有几个？如果有if判断怎么办？希望不吝赐教
------解决思路----------------------
基本操作是指
1）耗时最多，
2）完成任务所必需的操作
那些耗时很少的操作，可以忽略，不是任务必须的操作，可以精简，所以都不是基本操作
一般来说，
a）
循环的计数操作，多半不算基本操作，
循环条件判断的比较操作，
中和循环计数相关的，往往也不算基本操作。
b）基于比较的排序，一般交换（赋值）是基本操作，
如果赋值和比较相差比较小，比较也算作基本操作。否则比较不算基本操作。
c）
正常来说，循环体部分，往往是基本操作，
当然，C循环比较灵活
我们按照正常的循环，算就是了。
d）
复杂循环，会把大量工作，移到循环控制表达式中进行，
此时，循环控制表达式的计算，可能也是基本操作；
而一般循环的控制表达式的计算，多半不是基本操作。
e）基本操作，总是和具体实现相关的
对于同时有 ，频率接近的内存读写和文件读写来说，
文件读写更慢，是基本操作，内存读写，可以忽略。
这里说的快慢，通常指的是要相差1 到k 个数量级的（10^ 1~k,k>1），
------解决思路----------------------
不用纠结这种问题----除非你是数学家 要很精确........
从计算机的角度看，只要找嵌套最深的循环即可 即使你精确地计算出了一个算法的时间复杂度 最后还是最深的循环决定 其他都忽略了
------解决思路----------------------
无profiler不要谈效率！！尤其在这个云计算、虚拟机、模拟器、CUDA、多核 、多级cache、指令流水线、多种存储介质、……满天飞的时代！
------解决思路----------------------
流程控制语句，如果不是主要操作，流控表达式往往不是基本操作
if(c) s1; //表达式 c 往往不是基本操作
else s2; //这种看 s1,s2 是否比重相同，如果某个分支耗时很少，可以忽略这个分支。
正常情况下，s1,和s2 要同时计算时间复杂度。
细致的分析话，还要细分。
可能还要计算概率
if(c)s; 这种，通常只计算 s 即可
条件不满足，频度为0 ，满足频度为1，
在分析时间复杂度时，怎样找基本操作？基本操作可以有几个？如果有if判断怎么办？希望不吝赐教
------解决思路----------------------
基本操作是指
1）耗时最多，
2）完成任务所必需的操作
那些耗时很少的操作，可以忽略，不是任务必须的操作，可以精简，所以都不是基本操作
一般来说，
a）
循环的计数操作，多半不算基本操作，
循环条件判断的比较操作，
中和循环计数相关的，往往也不算基本操作。
b）基于比较的排序，一般交换（赋值）是基本操作，
如果赋值和比较相差比较小，比较也算作基本操作。否则比较不算基本操作。
c）
正常来说，循环体部分，往往是基本操作，
当然，C循环比较灵活
我们按照正常的循环，算就是了。
d）
复杂循环，会把大量工作，移到循环控制表达式中进行，
此时，循环控制表达式的计算，可能也是基本操作；
而一般循环的控制表达式的计算，多半不是基本操作。
e）基本操作，总是和具体实现相关的
对于同时有 ，频率接近的内存读写和文件读写来说，
文件读写更慢，是基本操作，内存读写，可以忽略。
这里说的快慢，通常指的是要相差1 到k 个数量级的（10^ 1~k,k>1），
------解决思路----------------------
不用纠结这种问题----除非你是数学家 要很精确........
从计算机的角度看，只要找嵌套最深的循环即可 即使你精确地计算出了一个算法的时间复杂度 最后还是最深的循环决定 其他都忽略了
------解决思路----------------------
无profiler不要谈效率！！尤其在这个云计算、虚拟机、模拟器、CUDA、多核 、多级cache、指令流水线、多种存储介质、……满天飞的时代！
------解决思路----------------------
流程控制语句，如果不是主要操作，流控表达式往往不是基本操作
if(c) s1; //表达式 c 往往不是基本操作
else s2; //这种看 s1,s2 是否比重相同，如果某个分支耗时很少，可以忽略这个分支。
正常情况下，s1,和s2 要同时计算时间复杂度。
细致的分析话，还要细分。
可能还要计算概率
if(c)s; 这种，通常只计算 s 即可
条件不满足，频度为0 ，满足频度为1，