#include <iostream>
using namespace std;
int main()
{
int a[100][100]={10};
cout<<a[0][0];
return 0;
}
Какова временная сложность вышеуказанной программы? это O (1) или O (100^2) ??временная сложность программы при инициализации 2D-массива?
Сложность времени постоянна, потому что рассмотрите выделение пространства malloc(sizeof(int)*rows*cols), где rows и cols были определены ранее.
Кроме того, индексирование массива происходит в постоянное время. Поэтому в целом он постоянный.
Все значения в вашем коде постоянны, поэтому его время выполнения постоянное: O (1).
(конечно, зависит фактическое время на машине вы решили запустить программу, а также от непредсказуемых внешних условий, как общая нагрузка системы во время выполнения.)
O(N) ,O(k) == O(1) (для постоянных k, k > 0).Поскольку ваш массив имеет фиксированный размер, сложность программы O(1).
если вы измените свою программу что-то вроде:
#include <iostream>
#include <vector>
int main()
{
int size;
std::cin >> size;
std::vector<int> a(size);
// ..
}
Там, инициализация a является O(N).
Инициализация массива таким образом выполняется компилятором во время компиляции, поэтому во время выполнения O (1) это O (1). –
Вышеупомянутый код не устанавливает все элементы в 10. Только 0 [0] будет 0 – user7
'O (100^2)' то же, что и 'O (1)'. – juanchopanza