Kitty喜欢小鱼干 发表于 2018-10-28 14:50:13

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


Kitty喜欢小鱼干 发表于 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>a )
                count++;
      }
    }
    printf("%d", count);
    return count;
}

int main(){
    int a = {5, 4, 3, 2, 1};
    NiXuNUM(a, 5);
    return 0;
}

claws0n 发表于 2018-10-28 15:17:50

归并排列，不要排列就可以计算逆序对。今天没电脑哈

Kitty喜欢小鱼干 发表于 2018-10-28 17:30:10

claws0n 发表于 2018-10-28 15:17
归并排列，不要排列就可以计算逆序对。今天没电脑哈

谢谢版主，我试试！！！{:5_108:}
页: [1]
查看完整版本: 请问怎么做到时间复杂度为O(nlogn)呢？谢谢解答。