1）计算算法频度T（n）假设算法的问题规模为n，例如对10个整数排序，问题规模为n就是10。算法频度是问题规模n的函数，用T(n)表示。算法执行时间大致等于原操作所需的时间XT(n)，也就是说T(n)与算法的执行时间成正比。为此用T（n)表示算法的执行时间。比较不同算法的T（n）大小得出算法执行时间的好坏。6/56
假设算法的问题规模为n，例如对10个整数排序，问题规模为n就是10。 算法频度是问题规模n的函数，用T(n)表示。 算法执行时间大致等于原操作所需的时间×T(n)，也就是说T(n)与算 法的执行时间成正比。为此用T(n)表示算法的执行时间。比较不同算 法的T(n)大小得出算法执行时间的好坏。 6/56
【例1.9】求两个n阶方阵的相加C=A+B的算法如下，求T(n)。执行次数void matrixadd(int][] A,int[][] B,int[j[] C,int n)n+11/语句①for (int i=o;i<n;i++)1语句②n(n+1)for(intj=o;j<n;j++)1语句?n2C[i][]=A[i][j]+B[i][j];7T(n)=n+1+n(n+1)+n2=2n2+2n+1。7/56
void matrixadd(int[][] A,int[][] B,int[][] C,int n) { for (int i=0;i<n;i++) //语句① for (int j=0;j<n;j++) //语句② C[i][j]=A[i][j]+B[i][j]; //语句③ } 【例1.9】求两个n阶方阵的相加C=A+B的算法如下，求T(n)。 执行次数 n+1 n(n+1) n 2 T(n)=n+1+n(n+1)+n 2 =2n 2+2n+1。 7/56
2）什么是算法时间复杂度算法中执行时间T(n)是问题规模n的某个函数f(n），记作：T(n) = o(f(n))执行时间cf(n)(T(n)ne8/56
算法中执行时间T(n)是问题规模n的某个函数f(n)，记作： T(n) = O(f(n)) cf(n) T(n) n0 n 执行时间 8/56
“0”的形式定义为：T(n）=o(f(n））表示存在一个正的常数，使得当n≥ng时都满足：IT(n) /≤clf(n) f(n)是T(n)的上界这种上界可能很多，通常取最接近的上界，即紧凑上界大致情况：T(n)1imf(n)n-009/56
“O”的形式定义为： T(n) = O(f(n))表示存在一个正的常数c，使得当n≥n0时都满足： |T(n)|≤c|f(n)| f(n)是T(n)的上界 这种上界可能很多，通常取最接 近的上界，即紧凑上界 大致情况： lim n→∞ T(n) f(n) = c 9/56
本质上讲，是一种T(n）提示最高数量级的比较也就是只求出T（n)的最高阶，忽略其低阶项和常系数，这样既可简化T(n)的计算，又能比较客观地反映出当n很大时算法的时间性能。10/56
也就是只求出T(n)的最高阶，忽略其低阶项和常系数，这样既可简化 T(n)的计算，又能比较客观地反映出当n很大时算法的时间性能。 本质上讲，是一种T(n) 提示 最高数量级的比较 10/56