Здравствуйте, хочу посчитать асимптотическую сложность алгоритма:
| C |
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
| struct findInfo *Search(struct peer *user, uint32_t peer_count, char *string, uint32_t hashTableSize, int32_t **graph, uint32_t user_index)
{
struct findInfo *list = infoListInit(peer_count);
if (list == NULL)
{
return NULL;
}
uint16_t *visited = malloc((peer_count + 1) * sizeof(uint16_t));
if (visited == NULL)
{
free(list);
return NULL;
}
for (uint16_t i = 0; i < peer_count + 1; i++)
{
list->prev[i] = user_index;
visited[i] = 0;
}
visited[0] = 1;
heapnode Node;
uint32_t currient_distance = 0;
int8_t check = 0;
uint32_t prev_id = user_index;
heap *Heap = DHT_heapInit(graph[user_index], peer_count);
if (Heap == NULL)
{
free(list);
free(visited);
return NULL;
}
list->prev[user_index] = user_index;
while (Heap->nnodes != 0)
{
Node = heap_extract_min(Heap);
currient_distance = Node.key;
visited[Node.value] = 1;
prev_id = Node.value;
if (lookupInPeerClose(user + Node.value - 1, string, hashTableSize) == 1)
{
list->distance = currient_distance;
list->index_peer = Node.value - 1;
list->string = string;
return list;
}
for (uint16_t j = 1; j <= peer_count; j++)
{
if (visited[j] == 0 && graph[Node.value - 1][j - 1] != -1)
{
check = heap_decrease_key(Heap, j, graph[Node.value - 1][j - 1] + currient_distance);
if (check != -1)
{
list->prev[j] = prev_id - 1;
}
}
}
}
free(list);
free(visited);
free(Heap);
return NULL;
} |
|
Если коротко , то тут инициализация кучи с n узлами, потом цикл while, внутри него цикл for, внутри него работа с кучей. Верно ли получается что сложность равна O(n^2 log n + nlogn) = O(n^2 log n) . Заранее спасибо.
(
