Является ли сложность времени моего проекта по Heapsort N * log (N)? - PullRequest
Новая
       11

Является ли сложность времени моего проекта по Heapsort N * log (N)?

0 голосов
/ 27 марта 2020

Я пытался написать "куча сортировки". Поэтому я сделал довольно простой C языковой проект. Но я удивился, почему сложность моего кода по времени равна O (N * log (N))? Я сравнил код других, и он кажется довольно похожим, поэтому я привел его сюда, чтобы получить совет.

Ниже мой код: 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int *intarray;
int size;
void heapify(int n, int max);
void heap_sort(int n);

//시간복잡도는 O(N * log N)
int main()
{
    scanf("%d", &size);
    intarray = (int *)malloc(sizeof(4 * (size + 1)));
    for (int i = 1; i <= size; i++)
        scanf("%d", &*(intarray + i));
    //입력끝
    heap_sort(size);
    for (int i = 1; i <= size; i++)
        printf(" [ %d ] ", intarray[i]);
    printf("프로그램종료");
    return 0;
}

void heapify(int n, int max)
{
    if (n > max)
        return;
    heapify(n * 2, max);
    heapify((n * 2) + 1, max);
    if (intarray[n] > intarray[n / 2] && n != 1) {
        int temp = intarray[n];
        intarray[n] = intarray[n / 2];
        intarray[n / 2] = temp;
    }
}

void heap_sort(int n)
{
    if (n < 1)
        return;
    heapify(1, n);
    int temp;
    temp = intarray[1];
    intarray[1] = intarray[n];
    intarray[n] = temp;
    heap_sort(n - 1);
}
...