C语言 Big-O，用于使用 for 循环插入 AVL

Question

我正在为我申请的公司编写代码示例，他们要求我的代码在最坏的情况下以 O（n） 运行。我决定使用 AVL 树，但要将我被赋予的值插入到 AVL 树中，我必须使用嵌套循环结构。这会使我的代码在最坏的情况下以 O（n²） 运行还是在 O（n log n） 中运行？

编辑：这是我的github上的代码链接：https://github.com/hsleiman1/Algorithms/blob/master/equilibriumIndexAVL.c

我的代码：

int equilibriumIndex(int A[], int N) {
    int i, newRoot = 1;
    while (newRoot < N) {
        node *leftTree = NULL;
        node *rightTree = NULL;
        for (i = 0; i < N; i++) {
            if (i == newRoot) continue;
            if (i < newRoot) leftTree = insert(leftTree, A[i]);
            if (i >= newRoot) rightTree = insert(rightTree, A[i]);
        }
        if (addSubTree(leftTree) == addSubTree(rightTree)) return newRoot;
        free(leftTree);
        free(rightTree);
        newRoot++;
    }
    return 0;
}
int addSubTree(node *subTree) {
     if (subTree == NULL)
         return 0;
     else
         return (subTree->value * subTree->repeat) + addSubTree(subTree->left) + addSubTree(subTree->right);
 }
 node *leafInit(node *leaf, int key) {
     leaf = (node*)malloc(sizeof(node));
     if (leaf != NULL) {
         leaf->value = key;
         leaf->left = NULL;
         leaf->right = NULL;
         leaf->repeat = 1;
     }
     return leaf;
 }
 node *insert(node *leaf, int key) {
     if (leaf == NULL) 
         leaf = leafInit(leaf, key);
     else if (key < leaf->value)
         leaf->left = insert(leaf->left, key);
     else
     if (key > leaf->value)
         leaf->right = insert(leaf->right, key);
     else
         leaf->repeat++;
     leaf = rotate(leaf, key);
     return leaf;
}
node *rotate(node *subTree, int key) {
     node *temp;
     int balance = getBalance(subTree);
     if (balance < -1) {
         temp = subTree->left;
         if (key > temp->value) {
             subTree->left = rightRotate(subTree->left);
             subTree = leftRotate(subTree);
         }
     } else
     if (balance > 1) {
         temp = subTree->right;
         if (key < temp->value) {
             subTree->right = leftRotate(subTree->right);
             subTree = rightRotate(subTree);
        }
     } else
     if (balance < -1 && key < subTree->value)
         subTree = leftRotate(subTree);
     else
     if (balance > 1 && key > subTree->value)
         subTree = rightRotate(subTree);
     return subTree;
 }
 node *leftRotate(node *leaf) {
     node *x = leaf->left;
     node *y = x->right;
     x->right = leaf;
     leaf->left = y;
     return x;
 }
 node *rightRotate(node *leaf) {
     node *x = leaf->right;
     node *y = x->left;
     x->left = leaf;
     leaf->right = y;
     return x;
 }
 int height(node *leaf) {
     if (leaf == NULL) return 0;
     else return max(height(leaf->left), height(leaf->right)) + 1;
 }
 int max(int num, int num1) {
     if (num < num1) return num1;
     else return num;
 }
 int getBalance(node *leaf) {
     return height(leaf->right) - height(leaf->left);
 }

Answer 1

使用 AVL 树永远不会让你变得 O（n） 复杂。如果你做对了，这可能很棘手，你会得到O（n.log（n）），如果你错过了，你可能会得到一个退化的树和O（n²）的复杂性。

对于 O（n） 复杂性，他们希望您使用哈希表。