我必须遍历一个大数组中的元素子集,其中每个元素指向另一个元素(问题来自于大图中连接组件的检测)。
我的算法如下: 1. 考虑第一个元素 2. 将下一个元素视为前一个元素指向的元素。3. 循环直到没有发现新元素 4. 考虑下一个元素在 1-3 中尚未考虑,回到 1。注意要考虑的元素数量远小于元素的总数。
对于我现在所看到的,我可以:
//create a map of all element, init all values to 0, set to 1 when consider
map<int,int> is_set; // is_set.size() will be equal to N
或者
//create a (too) large array (total size), init to 0 the elements to consider
int* is_set = (int*)malloc(total_size * sizeof(int)); // is_set length will be total_size>>N
我知道访问 map 中的键是 O(log N),而它只是数组的常量,但我不知道 malloc 在创建时是否成本更高,同时它还需要更多内存?