鱼C论坛

 找回密码
 立即注册
查看: 3083|回复: 3

请问怎么做到时间复杂度为O(nlogn)呢?谢谢解答。

[复制链接]
发表于 2018-10-28 14:50:13 | 显示全部楼层 |阅读模式
3鱼币
1.jpg

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

 楼主| 发表于 2018-10-28 15:02:08 | 显示全部楼层
#include <stdio.h>

//时间复杂度为O(n^2)
int NiXuNUM(int a[], int n){
    int i, j, count=0;

    for( i=0; i<n-1; i++ ){
        for( j=i+1; j<n; j++ ){
            if( a[i]>a[j] )
                count++;
        }
    }
    printf("%d", count);
    return count;
}

int main(){
    int a[5] = {5, 4, 3, 2, 1};
    NiXuNUM(a, 5);
    return 0;
}
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2018-10-28 15:17:50 From FishC Mobile | 显示全部楼层
归并排列,不要排列就可以计算逆序对。今天没电脑哈
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

 楼主| 发表于 2018-10-28 17:30:10 | 显示全部楼层
claws0n 发表于 2018-10-28 15:17
归并排列,不要排列就可以计算逆序对。今天没电脑哈

谢谢版主,我试试!!!
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-12-23 09:00

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表