数据结构与算法——算法时间复杂度


1. 大O记法

判断一个算法好不好,只通过少量的数据是不能做出准确判断的

T(n)= O(f(n))

在进行算法分析时,语句总的执行次数T(n)是关于问题规模n的函数,进而分析T(n)随n的变化情况并确定T(n)的数量级。算法的时间复杂度就是算法的时间量度,记为T(n)= O(f(n))

它表示某个算法,随着问题规模n的增大,算法执行时间的增长率和f(n)的增长率相同,称作算法的渐近时间复杂度,简称时间复杂度。f(n)为问题规模n的某个函数

这样用O()来体现算法时间复杂度的记法称为大O记法

显然,在一般情况下,随着n的增大,T(n)增长最慢的算法为最优算法

2. 推导大O阶方法

1.用常数1取代运行时间中的加法常数 2.修改后的运行次数函数中,只保留最高阶项 3.去掉最高阶项的系数(如果系数不为1)

这样就得到了大O阶

接下来是常见的大O阶

3. 常数阶

//执行一次
        int sum = 0,n=10;
        //执行一次
        sum =1+n;
        //执行一次
        System.out.println(sum);

运行次数f(n)=3

根据我们的推导方法,第一步就是把常改为1,在保留最高阶项发现它没有最高阶项,所以它的时间复杂度是O(1)

再者,如果sum=1+n;这个语句有十句,则会执行12次。事实上,无论n为多少,两者的差异就是3次和12次,与n的大小是无关的,不会随着n的变大而发生变化,执行时间恒定的算法,我们称为具有O(1)的时间复杂度,又叫常数阶

4. 线性阶

线性阶的循环结构会复杂很多。关键是分析循环结构的运行情况

for (int i = 0; i < n; i++) {
            // 时间复杂度为O(1)的程序步骤序列
}

循环时间复杂度为O(n),因为循环体中的代码要执行n次

5. 对数阶

int count = 1;
        while(count <n){
            count = count*2;
            //时间复杂度为O(1)的程序步骤序列
        }

由于每次count*2以后,就距离n更近了,当多少个2相乘以后大于n,就会退出循环

由2^x=n得到x=log2(n),所以这个循环的时间复杂度为O(logn)

6. 平方阶

看一个循环嵌套

for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                //时间复杂度为O(1)的程序步骤序列
            }
        }

内循环为O(n),对于外循环,不过是内部时间复杂度为O(n)的语句在循环n次,所以时间复杂度为O(n^2)

如果循环次数改为m,时间复杂度就变为O(m*n)

7. 分析时间复杂度

下面我们看几段代码分析一下时间复杂度

7.1func1的时间复杂度

// 计算func1的时间复杂度?
        void func1(int N) {
            int count = 0;
            for (int k = 0; k < 2 * N ; k++) {
                count++;
            }
            int M = 10;
            while ((M--) > 0) {
                count++;
            }
            System.out.println(count);
        }

基本操作执行了2N+10次,通过推导大O阶方法知道,时间复杂度为 O(N)

7.2 func2的时间复杂度

// 计算func2的时间复杂度?
void func2(int N) {
int count = 0;
for (int k = 0; k < 100; k++) {
count++;
}
System.out.println(count);
}

基本操作执行了100次,通过推导大O阶方法,时间复杂度为 O(1)

7.3 binarySearch的时间复杂度

// 计算binarySearch的时间复杂度?
int binarySearch(int[] array, int value) {
            int begin = 0;
            int end = array.length - 1;
            while (begin <= end) {
                int mid = begin + ((end-begin) / 2);
                if (array[mid] < value)
                    begin = mid + 1;
                else if (array[mid] > value)
                    end = mid - 1;
                else
                    return mid;
            }
            return -1;
        }

基本操作执行最好1次,最坏 log2(n)次,时间复杂度为 O(log2(n)) ps: og2(n)在算法分析中表示是底数 为2,对数为N,有些地方会写成lgN。(因为二分查 找每次排除掉一半的不适合值,一次二分剩下:n/2 两次二分剩下:n/2/2 = n/4)。即n/(2^x),x=logn

7.4 阶乘递归factorial的时间复杂度

// 计算阶乘递归factorial的时间复杂度?
long factorial(int N) {
return N < 2 ? N : factorial(N-1) * N;
}

递归的时间复杂度=递归次数*每次递归之后执行的次数

基本操作递归了N次,时间复杂度为O(N)

7.5 斐波那契递归fibonacci的时间复杂度

// 计算斐波那契递归fibonacci的时间复杂度?
int fibonacci(int N) {
return N < 2 ? N : fibonacci(N-1)+fibonacci(N-2);
}

参考一下斐波那契数的递归图

分析发现基本操作递归了2^n 次,时间复杂度为O( 2^n)

7.6 bubbleSort的时间复杂度

// 计算bubbleSort的时间复杂度?
void bubbleSort(int[] array) {
            for (int end = array.length; end > 0; end--) {
                boolean sorted = true;
                for (int i = 1; i < end; i++) {
                    if (array[i - 1] > array[i]) {
                        Swap(array, i - 1, i);
                        sorted = false;
                    }
                }
                if (sorted == true) {
                    break;
                }
            }
        }

基本操作执行最好N次,最坏执行了(N*(N-1))/2次,通过推导大O阶方法+时间复杂度一般看最坏,时间 复杂度为 O(N^2)

原创文章,作者:ItWorker,如若转载,请注明出处:https://blog.ytso.com/291021.html

(0)
上一篇 2022年10月14日
下一篇 2022年10月14日

相关推荐

发表回复

登录后才能评论