#G116. GESP level5 算法复杂度估算方法

GESP level5 算法复杂度估算方法

GESP level5 - 算法复杂度估算方法

  1. 下面C++代码中的isPrimeA()和isPrimeB()都用于判断参数N是否素数,有关其时间复杂度的正确说法是( )?
bool isPrimeA(int N){
    if(N<2)
        return false;
    for(int i=2;i<N;i++)
        if(N%i==0)
            return false;
    return true;
}
bool isPrimeB(int N){
    if(N<2)
        return false;
    int endNum=int(sqrt(N));
    for(int i=2;i<=endNum;i++)
        if(N%i==0)
            return false;
    return true;
}

{{ select(1) }}

  • isPrimeA()的最坏时间复杂度是O(N/2),isPrimeB()的最坏时间复杂度是O(logN),isPrimeA()优于isPrimeB()
  • isPrimeA()的最坏时间复杂度是O(N),isPrimeB()的最坏时间复杂度是O(√N),isPrimeB()绝大多数情况下优于isPrimeA()
  • isPrimeA()的最坏时间复杂度是O(√N),isPrimeB()的最坏时间复杂度是O(N),isPrimeA()优于isPrimeB()
  • isPrimeA()的最坏时间复杂度是O(logN),isPrimeB()的最坏时间复杂度是O(N),isPrimeA()优于isPrimeB()
  1. 下面代码中的isPrimeA()和isPrimeB()都用于判断参数N是否素数,有关其时间复杂度的正确说法是( )?
#include 
#include
using namespace std;

bool isPrimeA(int N){
    if(N<2)
        return false;
    for(int i=2;i<N;i++)
        if(N%i==0)
            return false;
    return true;
}
bool isPrimeB(int N){
    if(N<2)
        return false;
    int endNum=int(sqrt(N));
    for(int i=2;i<=endNum;i++)
        if(N%i==0)
            return false;
    return true;
}

int main(){
    cout<<boolalpha;
    cout<<isPrimeA(13)<<" "<<isPrimeB(13)<<end1;
    return 0;
}

{{ select(2) }}

  • isPrimeA()的最坏时间复杂度是O(N),isPrimeB()的最坏时间复杂度是O(log N),isPrimeB()优于isPrimeA()
  • isPrimeA()的最坏时间复杂度是O(N),isPrimeB()的最坏时间复杂度是O(N½),isPrimeB()优于isPrimeA()
  • isPrimeA()的最坏时间复杂度是O(N½),isPrimeB()的最坏时间复杂度是O(N),isPrimeA()优于isPrimeB()
  • isPrimeA()的最坏时间复杂度是O(log N),isPrimeB()的最坏时间复杂度是O(N),isPrimeA()优于isPrimeB()
  1. 下面关于算法复杂度的说法,正确的是( )? {{ select(3) }}
  • 算法复杂度只包括时间复杂度
  • 时间复杂度为O(n)的算法一定比时间复杂度为O(n²)的算法运行速度快
  • 空间复杂度指的是算法在运行过程中所占用的所有空间
  • 计算时间复杂度时,通常关注的是算法在最坏情况下的运行时间
  1. 下面函数可以将n的所有质因数找出来,其时间复杂度是( )?
#include 
#include 
vector get_prime_factors(int n){
    vector factors;
    while (n%2==0){
        factors.push_back(2);
        n/=2;
    }
    for(int i=3;i*i2){
        factors.push_back(n);
    }
    return factors;
}

{{ select(4) }}

  • O(n²)
  • O(n)
  • O(√n)
  • O(log n)
  1. 假设快速排序算法的输入是一个长度为n的已排序数组,且该快速排序算法在分治过程总是选择第一个元素作为基准元素。下面选项( )描述的是在这种情况下的快速排序行为? {{ select(5) }}
  • 快速排序对于此类输入的表现最好,因为数组已经排序
  • 快速排序对于此类输入的时间复杂度是O(n log n)
  • 快速排序对于此类输入的时间复杂度是O(n²)
  • 快速排序无法对此类数组进行排序,因为数组已经排序
  1. 考虑以下C++代码实现的归并排序算法:
void merge(int arr[], int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;
    int L[n1], R[n2];
    for (int i = 0; i < n1; i++)
        L[i] = arr[left + i];
    for (int j = 0; j < n2; j++)
        R[j] = arr[mid + 1 + j];
    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}
void merge_sort(int arr[], int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;
        merge_sort(arr, left, mid);
        merge_sort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
}

对长度为n的数组arr,调用函数merge_sort(a, 0, n - 1),在排序过程中merge函数的递归调用次数大约是( )? {{ select(6) }}

  • O(n)
  • O(n log n)
  • O(log n)
  • O(n²)
  1. 现在用如下代码来计算x的n次方(n个x相乘),其时间复杂度为( )?
double quick_power(double x, unsigned n) {
    if (n == 0) return 1;
    if (n == 1) return x;
    return quick_power(x, n / 2) * quick_power(x, n / 2) * ((n & 1)? x : 1);
}

{{ select(7) }}

  • O(n)
  • O(log n)
  • O(n²)
  • O(n log n)
  1. 下列代码中,函数f的作用是( )?
void f(int a, int b)
    return b==0?a:f(b,a %b);
}

{{ select(8) }}

  • 求a和b的最大公共质因子
  • 求a和b的最小公共质因子
  • 求a和b的最大公约数
  • 求a和b的最小公倍数
  1. 下面C++代码用于有序list的二分查找,有关说法错误的是( )?
int _binarySearch(vector lst, int Low, int High, int Target) {
    if (Low > High)
        return -1;
    int Mid = (Low + High) / 2;
    if (Target == lst[Mid])
        return Mid;
    else if (Target < lst[Mid])
        return _binarySearch(lst, Low, Mid - 1, Target);
    else
        return _binarySearch(lst, Mid + 1, High, Target);
}
int bSearch(vector lst, int Val) {
    return _binarySearch(lst, 0, lst.size(), Val);
}

{{ select(9) }}

  • 代码采用二分法实现有序list的查找
  • 代码采用分治算法实现有序list的查找
  • 代码采用递归方式实现有序list的查找
  • 代码采用动态规划算法实现有序list的查找
  1. 在上题的_binarySearch算法中,如果lst中有N个元素,其时间复杂度是( )? {{ select(10) }}
  • O(N)
  • O(logN)
  • O(NlogN)
  • O(N²)
  1. 下面关于归并排序,描述正确的是( )? {{ select(11) }}
  • 归并排序是一个不稳定的排序算法
  • 归并排序的时间复杂度在最优、最差和平均情况下都是O(n log n)
  • 归并排序需要额外的O(1)空间
  • 对于输入数组{12, 11, 13, 5, 6, 7},代码输出结果为:7 6 5 13 12 11
  1. 对下面两个函数,说法错误的是( )?
int sumA(int n) {
    int res = 0;
    for (int i = 1; i <= n; i++) {
        res += i;
    }
    return res;
}
int sumB(int n) {
    if (n == 1)
        return 1;
    int res = n + sumB(n - 1);
    return res;
}

{{ select(12) }}

  • sumA体现了迭代的思想
  • SumB采用的是递归方式
  • SumB函数比SumA的时间效率更高
  • 两个函数的实现的功能相同
  1. 下面关于算法复杂度的说法,正确的是( )? {{ select(13) }}
  • 算法复杂度只包括时间复杂度
  • 时间复杂度为O(n)的算法一定比时间复杂度为O(n²)的算法运行速度快
  • 空间复杂度指的是算法在运行过程中所占用的所有空间
  • 计算时间复杂度时,通常关注的是算法在最坏情况下的运行时间
  1. 下述代码实现素数表的线性筛法,筛选出所有小于等于n的素数,下面说法正确的是( )?
vector sieve_linear(int n) {
    vector is_prime(n + 1, true);
    vector primes;
    for (int i = 2; i <= n; ++i) {
        if (is_prime[i]) {
            primes.push_back(i);
        }
        for (int j = 0; j < primes.size() && i * primes[j] <= n; ++j) {
            is_prime[i * primes[j]] = false;
            if (i % primes[j] == 0) {
                break;
            }
        }
    }
    return primes;
}

{{ select(14) }}

  • 线性筛的时间复杂度是O(n log log n)
  • 每个合数会被其所有的质因子标记一次
  • 线性筛和埃拉托斯特尼筛的实现思路完全相同
  • 线性筛的时间复杂度是O(n)
  1. 在快速排序中,选择的主元素(pivot)会影响算法的( )? {{ select(15) }}
  • 不影响
  • 时间复杂度
  • 空间复杂度
  • 时间复杂度和空间复杂度
  1. 归并排序的基本思想是( )? {{ select(16) }}
  • 将数组分成两个子数组,分别排序后再合并
  • 随机选择一个元素作为枢轴,将数组划分为两个部分
  • 从数组的最后一个元素开始,依次与前一个元素比较并交换位置
  • 比较相邻的两个元素,如果顺序错误就交换位置
  1. 下面C++代码用于排序,下列说法中错误的是( )?
void sortA(int*arr, int n) {
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j  arr[j + 1]) {
                int tmp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = tmp;
            }
        }
    }
}
void sortB(int*arr, int start, int end) {
    if (start >= end)
        return;
    int middle = (start + end) / 2;
    sortB(arr, start, middle);
    sortB(arr, middle + 1, end);
    int leftSize = middle - start + 1;
    int rightSize = end - middle;
    int*left = new int[leftSize];
    int*right = new int[rightSize];
    for (int i = 0; i < leftSize; i++)
        left[i] = arr[start + i];
    for (int j = 0; j < rightSize; j++)
        right[j] = arr[middle + 1 + j];
    int i = 0, j = 0, k = start;
    while (i < leftSize && j < rightSize) {
        if (left[i] <= right[j])
            arr[k++] = left[i++];
        else
            arr[k++] = right[j++];
    }
    while (i < leftSize)
        arr[k++] = left[i++];
    while (j < rightSize)
        arr[k++] = right[j++];
    delete[] left;
    delete[] right;
}

{{ select(17) }}

  • 两种排序算法的时间复杂度不同
  • 两种排序算法的空间复杂度一致
  • sortA的时间复杂度在最好和最坏情况下都是O(n²)
  • sortB的平均时间复杂度、最好情况的时间复杂度都是O(n log n),最坏情况的时间复杂度是O(n²)
  1. 上一题中的sortB函数,明显体现出的算法思想和编程方法包括( )? {{ select(18) }}
  • 递归
  • 分治
  • A、B都正确
  • A、B都不正确
  1. 下列哪个算法并没有体现分治思想?( ) {{ select(19) }}
  • 二分查找
  • 埃氏筛法
  • 归并排序
  • 快速排序
  1. 下面关于链表和数组的描述,错误的是( )? {{ select(20) }}
  • 数组大小固定,链表大小可动态调整
  • 数组支持随机访问,链表只能顺序访问
  • 存储相同数目的整数,数组比链表所需的内存多
  • 数组插入和删除元素效率低,链表插入和删除元素效率高
  1. 考虑以下C++代码实现的二分查找算法:
int binarySearch(vector& nums, int target, int left, int right) {
    if (left > right) {
        return -1;
    }
    int middle = left + ((right - left) / 2);
    if (nums[middle] == target) {
        return middle;
    }
    else if (nums[middle] < target) {
        return binarySearch(nums, target, middle + 1, right);
    }
    else {
        return binarySearch(nums, target, left, middle - 1);
    }
}
int Find(vector& nums, int target) {
    int n = nums.size();
    return binarySearch(nums, target, 0, n - 1);
}

关于上述函数,描述不正确的是( )? {{ select(21) }}

  • 函数采用二分查找,每次计算搜索当前搜索区间的中点,然后根据中点的元素值排除一半搜索区间
  • 函数采用递归求解,每次问题的规模减小一半
  • 递归的终止条件是中间元素的值等于target,若数组中不包含该元素,递归不会终止
  • 算法的复杂度为O(log n)
  1. 给定一个长度为n的有序数组nums,其中可能包含重复元素。下面的函数返回数组中某个元素target的左边界,若数组中不包含该元素,则返回−1。例如在数组nums = [5,7,7,8,8,10]中查找target=8,函数返回在数组中的左边界的索引为3。则横线上应填写的代码为( )?
int getLeftBoundary(vector& nums, int target) {
    int left = 0;
    int right = nums.size() - 1;
    while (left < right) {
        int middle = left + ((right - left) / 2);
        if (target <= nums[middle]) {
            // 在此处填入代码
        }
        else {
            left = middle + 1;
        }
    }
    return nums[left] == target ? left : -1;
}

{{ select(22) }}

  • right = middle - 1
  • right = middle
  • right = middle + 1
  • 以上都不对
  1. 假设有n个人要过河,每只船最多载2人,船的承重为100kg。下列代码中,数组weight中保存有n个人的体重(单位为kg),已经按从小到大排好序,代码输出过河所需要的船的数目,采用的思想为( )?
int i, j;
int count = 0;
for (i = 0, j = n - 1; i < j; j--) {
    if (weight[i] + weight[j] <= 100) {
        i++;
    }
    count++;
}
printf("过河的船数:%d\n", count);

{{ select(23) }}

  • 枚举算法
  • 贪心算法
  • 迭代算法
  • 递归算法
  1. 关于分治算法,以下哪个说法正确? {{ select(24) }}
  • 分治算法将问题分成子问题,然后分别解决子问题,最后合并结果
  • 归并排序不是分治算法的应用
  • 分治算法通常用于解决小规模问题
  • 分治算法的时间复杂度总是优于O(n log (n))
  1. 根据下述二分查找法,在排好序的数组1,3,6,9,17,31,39,52,61,79中查找数值31,循环while (left <= right)执行的次数为( )?
int binary_search(vector& nums, int target) {
    int left = 0;
    int right = nums.size() - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            return mid;
        }
        else if (nums[mid] < target) {
            left = mid + 1;
        }
        else {
            right = mid - 1;
        }
    }
    return -1;
}

{{ select(25) }}

  • 1
  • 2
  • 3
  • 4
  1. 以下关于高精度运算的说法错误的是( )? {{ select(26) }}
  • 高精度计算主要是用来处理大整数或需要保留多位小数的运算
  • 大整数除以小整数的处理的步骤可以是,将被除数和除数对齐,从左到右逐位尝试将除数乘以某个数,通过减法得到新的被除数,并累加商
  • 高精度乘法的运算时间只与参与运算的两个整数中长度较长者的位数有关
  • 高精度加法运算的关键在于逐位相加并处理进位
  1. 当n=7时,下面函数的返回值为( )?
int fun(int n) {
    if (n == 1)
        return 1;
    else if (n >= 5)
        return n * fun(n - 2);
    else
        return n * fun(n - 1);
}

{{ select(27) }}

  • 105
  • 840
  • 210
  • 420
  1. 下面关于递归的说法,错误的是( )? {{ select(28) }}
  • 递归函数必须有终止条件
  • 递归函数每次调用自身时,参数应向终止条件靠拢
  • 递归的空间复杂度一定比迭代高
  • 所有递归函数都可以用迭代方式实现
  • 快速排序算法不可以用迭代方式实现
  1. 对下面两个函数,说法错误的是( )?
int fibA(int n) {
    if (n <= 1)
        return n;
    int f1 = 0, f2 = 1;
    for (int i = 2; i <= n; ++i) {
        int temp = f2;
        f2 = f1 + f2;
        f1 = temp;
    }
    return f2;
}
int fibB(int n) {
    if (n <= 1)
        return n;
    return fibB(n - 1) + fibB(n - 2);
}

{{ select(29) }}

  • 两个函数的实现的功能相同
  • fibA采用递推方式
  • fibB采用的是递归方式
  • fibA时间复杂度为O(n),fibB的时间复杂度为O(n²)
  1. 若用二分法在[1, 100]内猜数,最多需要猜( )次? {{ select(30) }}
  • 100
  • 10
  • 7
  • 5