Барномаи шумо чӣ қадар тез аст?

Қадамҳои барномаро барои бузургтарин вуруд ҳисоб кунед, онҳоро бо тақрибан 10⁸ қадам дар сония муқоиса кунед ва барномаи суств коркардро ислоҳ кунед.

Назария

Дарси 6 аз 7

Хониш: 15 дақиқа

Саволҳо: 5

Қадамҳоро мешуморем

Мо сонияҳоро намешуморем, зеро онҳо аз компютер вобастаанд. Мо қадамҳо-ро мешуморем: амалҳои оддӣ, мисли ҷамъ, муқоиса, хондан ё тағйир додани як катак. Муҳим он аст, ки шумораи қадамҳо бо андозаи n-и вуруд чӣ тавр меафзояд.

a[i] = 7; ё cout << a[p - 1]; чанд қадам мегирад, барои ҳар n яксон.
Сикл аз болои вектор тақрибан n қадам мегирад.
Ду сикл пай дар пай тақрибан 2n мегиранд: боз ҳам «тақрибан n».
Сикле, ки дар ҳар гузариш тамоми сикли векторро иҷро мекунад, тақрибан n · n = n² мегирад.

Қоидаи тахминӣ: компютер дар як сония тақрибан 10⁸ қадами оддӣ мекунад. Ин қоидаи дағал аст, аммо барои нақшакашӣ бехатар. Барои n = 10⁵, n қадам як ҳазорӯми сония мегирад. n² 10¹⁰ қадам аст: тақрибан 100 сония, хеле аз маҳдудият зиёд.

Маҳдудиятҳо мегӯянд, ки чӣ қадар тез бояд буд

Ҳар шарт калонтарин вурудро медиҳад, мисли 1 ≤ n ≤ 10⁵. Онро пеш аз навиштани код ба ҳисоби қадамҳо гузоред:

n то 5000: n² ба 2,5 · 10⁷ баробар аст, дар як сония хуб аст;
n то 10⁵: n² ба 10¹⁰ баробар аст, хеле суст. Танҳо тақрибан n қадам ҷой мешавад, чанд гузариш;
n то 10⁶: n² ба 10¹² баробар аст, ва n қадам вуруди зудро талаб мекунад.

Маҳдудияти 10⁵ оромона мегӯяд: «як гузариш, ё чанд гузариш: на сикл аз болои ҳама барои ҳар ҷузъ». Маҳдудияти 1000 ё 5000 аксар баръаксро мегӯяд: сикл барои ҳар ҷузъ интизор меравад.

Сикле, ки ҳар дафъа тамоми сиклро иҷро мекунад

Барномаи суст аксаран як шакл дорад: барои ҳар ҷузъ он боз аз ҳамаи ҷузъҳо мегузарад.

Кинотеатр чиптаҳоро бо рақамҳои 1 то n фурӯхт. Баъд аз намоиш n - 1-и онҳо, бо тартиби дилхоҳ, баргардонида шуданд. Кадом чипта намерасад?

Ғояи аввал: ҳар адади k-ро аз 1 то n санҷед ва онро дар байни чиптаҳо ҷӯед. Онро бо ҳисобкунак қадам ба қадам гузаред:

Роҳи суст: барои ҳар адад тамоми векторро ҷустан

C++

1#include <bits/stdc++.h>

2using namespace std;

4int main() {

5 ios_base::sync_with_stdio(false);

6 cin.tie(NULL);

8 vector<int> a = {3, 1};

9 int n = 3, checks = 0;

10 for (int k = 1; k <= n; k++) {

11 bool found = false;

12 for (int i = 0;

13 i < n - 1; i++) {

14 checks++;

15 if (a[i] == k) {

16 found = true;

17 }

18 }

19 if (!found) {

20 cout << k << "\n";

21 }

22 }

23 cout << checks << " checks\n";

24 return 0;

25}

Чиптаҳо

сатр 8

Чиптаҳои 1 то 3 фурӯхта шуданд, ва ду баргашт: 3 ва 1. Кадомаш намерасад?

a2 катак

n—checks—k—found—i—

1 / 37

Барномаи шумо чӣ қадар тез аст?

Қадамҳоро мешуморем

Маҳдудиятҳо мегӯянд, ки чӣ қадар тез бояд буд

Сикле, ки ҳар дафъа тамоми сиклро иҷро мекунад

Машқ: мураккабии вақтӣ

Борҳо такрор кардани қадами хурд

Ҷавобро нав нигоҳ доред

O(1), O(n), O(n²)

Сиклҳои дохилӣ: чанд қадам?

Худатон иҷро кунед

Худро санҷед

Вазифаи хонагӣ

Хулоса