什么是"渐近紧时间复杂度"？此代码的时间复杂度是否渐近紧张？

Question

为什么这个代码的时间复杂度是O（xnm）？

此代码的时间复杂度是否渐近紧张？

为什么？

#include<conio.h>
#include<iostream>
using namespace std;
int main()
{
    int a[10][10], b[10][10], c[10][10];
    int x, y, i, j, m, n;

    cout << "nEnter the number of rows and columns for Matrix A:::nn";
    cin >> x >> y;

    // x denotes number rows in matrix A
    // y denotes number columns in matrix A
    cout << "nnEnter elements for Matrix A :::nn";
    for (i = 0; i < x; i++)
    {
        for (j = 0; j < y; j++)
        {
            cin >> a[i][j];
        }
        cout << "n";
    }
    cout << "nnMatrix A :nn";
    for (i = 0; i < x; i++)
    {
        for (j = 0; j < y; j++)
        {
            cout << "t" << a[i][j];
        }
        cout << "nn";
    }
    cout << "n-----------------------------------------------------------n";
    cout << "nEnter the number of rows and columns for Matrix B:::nn";
    cin >> m >> n;
    // m denotes number rows in matrix B
    // n denotes number columns in matrix B

    cout << "nnEnter elements for Matrix B :::nn";
    for (i = 0; i < m; i++)
    {
        for (j = 0; j < n; j++)
        {
            cin >> b[i][j];
        }
        cout << "n";
    }
    cout << "nnMatrix B :nn";
    for (i = 0; i < m; i++)
    {
        for (j = 0; j < n; j++)
        {
            cout << "t" << b[i][j];
        }
        cout << "nn";
    }
    if (y == m)
    {
        for (i = 0; i < x; i++)
        {
            for (j = 0; j < n; j++)
            {
                c[i][j] = 0;
                for (int k = 0; k < m; k++)
                {
                    c[i][j] = c[i][j] + a[i][k] * b[k][j];
                }
            }
        }
        cout
                << "n-----------------------------------------------------------n";
        cout << "nnMultiplication of Matrix A and Matrix B :nn";
        for (i = 0; i < x; i++)
        {
            for (j = 0; j < n; j++)
            {
                cout << "t" << c[i][j];
            }
            cout << "nn";
        }
    }
    else
    {
        cout << "nnMultiplication is not possible";
    }
    getch();
    return 0;
}

Answer 1

因为大多数计算都是在这里完成的：

for (i = 0; i < x; i++)
    {
        for (j = 0; j < n; j++)
        {
            c[i][j] = 0;
            for (int k = 0; k < m; k++)
            {
                c[i][j] = c[i][j] + a[i][k] * b[k][j];
            }
        }
    }

这里加法、乘法和赋值等基本运算的近似数是x*n*m 。这就是为什么这个算法O(x*n*m)渐近的原因。但是矩阵乘法在渐近方面可以做得更快。只需查看有关矩阵乘法和大o表示法的相关文章。

复杂性介绍

更快的矩阵乘法