算法复杂度是怎么计算的（算法及算法复杂度）
算法复杂度是怎么计算的（算法及算法复杂度）时间复杂度可简单理解为：算法中各条指令的执行时间之和。输入规模：用以描述输入所需的空间规模。算法的4大特性：1.时间复杂度（timecomplexity）度量 执行时间与输入规模之间的一个函数。y:执行时间 x:输入规模 -----表现形式T(n) ：时间复杂度
定义：
指基于特定的计算模型，旨在解决某一信息处理问题而设计的一个指令序列。
算法的演变：
实际应用问题--抽象数学描述---抽象关系描述与表达（建模）---算法的输入（input）与输出（output）的确定----算法步骤的描述---算法的确定性和可行性分析---算法的有穷性（finiteness）和确定性（correctness）分析---算法的退化（degeneracy）和鲁棒性（robustness）分析----算法的重用性和可移植性分析
算法的4大特性：
- 可计算性
- 难解性
- 计算效率（可解、非不可解和难解）
- 数据结构（以“数据”这一信息的表现形式为研究对象，旨在建立支持高效算法的shuj数据信息处理策略、技巧和方法）
1.时间复杂度（timecomplexity）度量
执行时间与输入规模之间的一个函数。y:执行时间 x:输入规模 -----表现形式T(n) ：时间复杂度
输入规模：用以描述输入所需的空间规模。
时间复杂度可简单理解为：算法中各条指令的执行时间之和。
在图灵机（Turing Machine TM）和随机存储机（Random Access Machine RAM）等计算模型中，指令语句均可分解为若干次基本操作。T(n)可表示为 算法所执行基本操作的总次数。
2.渐进复杂度分析（asymptotic analysis）
实现同一问题的不同算法之间不同规模之间执行时间的比较分析。
------表现形式：T(n)、大O记号（big-o notation）.
基于大O记号、环境差异、基本操作等因素的综合分析。
3.空间复杂度（space complexity）
空间复杂度主要指算法存储空间性能指标，即算法占用储存空间的多少。 可用类似时间复杂度的相关符号描述。
1.常数时间复杂度算法 o(1) [constant-time algorithm]
实例： 常规元素的选取问题[任意三个元素排序，输出非极端元素]
分析：输入---输入三个元素，三次操作o（3）-----比较三个元素，最多三次操作o（3）-----输出非极端元素，一次操作o（1）----输出。
计算： T（n） = o（3） o（3） o（1）= o（7） = o（1）
2.对数多项式时间复杂度算法o（logn） [polylogarithmic-time algorithm]
实例： 对于任意非负整数，统计其二进制展开中位数1的总数。
分析：输入-- 输入计数器d 非负整数n----d=0，通过二进制位的与运算，检查你的二进制展开的最低位 是1则累计到d中----输出计数器d---输出
计算：o（1 [log2 n]） = o （[log 2 n]） = o（log2 n）
3.线性时间复杂度o（n） [ linear-time algorithm]
实例： 计算给定n个整数的总和。
分析：输入-- 输入累计器sum 整数n----sum=0 通过数组元素求和算法（循环迭代），累计sum------输出sum--------输出
计算：o（1） o （1）* n = o（n 1） = o（n）
4.多项式时间复杂度o（polynomial(n)） [ polynomial-time algorithm ]
定义：运行时间可以表示为和度量为T(n) = o(f(n))的形式。例如：f(n) = 2[n] (2的n次幂)等
5.指数时间复杂度 [ exponential-time algorithm ]
实例：在禁止超过1位的位移运算的前提下，对任意非负整数n 计算幂
分析：迭代运算
_int64 power2BF_I (int n) //幂函数算法（蛮力迭代版） 输入参数 n (n>=0) { _int64 pow = 1 ; //o(1) :累积器初始化为2的零次幂 while (0<n--) //o(n) : 迭代n轮 pow<<=1 ; // o(1) : 将累积器翻倍 return pow ; //o(1) : 返回累积器 } //o(n) =o(2^r) r 为输入指数n的比特位数
计算：o（n）= o（2^r）
注：
非有效算法：不指定运行指数量级的指数复杂度算法无法真正应用于实际问题中，故此称为非有效算法。
难解问题：不存在多项式复杂度算法的问题。
典型的复杂度层次:
o(1)、o(log* n) 、o(loglogn)、o(logn)、o(sqrt(n))、o(n)、o(nlog*n)、o(nloglogn)、o(nlogn)、o(n^2)、o(n^3)、o(n^c)、o(2^n)等。
