際際滷

際際滷Share a Scribd company logo

Algo 01 part01

Download as PPTX, PDF
Alex Tarasov
Alex Tarasov
1 of 25
Download to read offline
CV_RTF: algo posidelky 束亠仆从舒 仍仂亢仆仂亳 舒仍亞仂亳仄仂于損
舒亠仄?
舒亠仄? 亞舒仆亳亠仆仆仂 亠仂于: ∃亠仄 ∃舒仄
舒从 仂亠仆亳 从仂仂?
舒从 仂亠仆亳 从仂仂? MatLAB 亠 仗亠亳舒仍仆亶 亳仆仄亠仆 仂亟: A = ones(500,500); B = ones(500,500) * 2; C = zeros(500,500); tic C = A .* B; toc % ====== tic for i = 1 : 500 for j = 1 : 500 C(i,j) = A(i, j) * B(i, j); end end toc
舒从 仂亠仆亳 从仂仂? MatLAB 亠 仗亠亳舒仍仆亶 亳仆仄亠仆 于仂亟: Elapsed time is 0.000822 seconds. Elapsed time is 0.008758 seconds.
舒从 仂亠仆亳 从仂仂? 弌++ 仄仂亢仆仂 仆舒仗亳舒 从仂仍! #include <ctime> clock_t time = clock(); // algorithm double delta = (double)(clock() time); delta /= CLOCKS_PER_SEC; cout << Time is << delta << endl;
舒从 仂亠仆亳 从仂仂? 仂弍亠仄 仍舒亠 于 亰舒[fail]亳亠, 仗仂仂仄 仂: ∃仂亟仆亠 亟舒仆仆亠 舒亰仆亠 ∃亠舒仍亳亰舒亳 亢亠仍亠亰舒 舒亰仆舒 仂仄仗舒仆亳 Reca 于仗从舒亠 仄仂仆亳仂, 弍仂仍仂亶 仗仂仗仍仆仂 仗仂仍亰亠 亳 仄仂亟亠仍 AB999 舒亰仄亠舒仄亳 从舒仆舒 ab 舒仆亳仄亠仂于. 亰-亰舒 仂仂弍亠仆仆仂亠亶 仗仂亳亰于仂亟于舒, 舒亰仄亠 从舒仆舒 于舒亢舒ﾑ 亠仍仄 亳仍仂仄 舒仆亳仄亠仂于. 亠亟舒于仆仂 于 仄仂亟 于仂仍仂 仂仂仆仂亠仆亳亠 仂仂仆 x:y. 仂仄仗舒仆亳 仂亠 仄亠仆亳 舒亰仄亠 从舒仆舒 于仂亠亞仂 仄仂仆亳仂舒 AB999 舒从, 仂弍 亠亞仂 仂仂仆仂亠仆亳亠 仂仂仆 舒仍仂 x:y, 仆仂 仗亳 仂仄 亠亞仂 仗仍仂舒亟 弍仍舒 仄舒从亳仄舒仍仆仂 于仂亰仄仂亢仆仂亶. 舒舒 亰舒亟舒舒 仂仗亠亟亠仍亳 舒亰仄亠 从舒仆舒 仄亠仆亠仆仆仂亶 仄仂亟亠仍亳, 亳仍亳 于仆亳, 仂 仂 亟亠仍舒 仆亠于仂亰仄仂亢仆仂. 仗亠于仂亶 仂从亠 于仂亟仆 亟舒仆仆 仂亟亠亢舒 4 亠仍 亳仍舒 a, b, x 亳 y (1a,b,x,y2揃109). http://codeforces.ru/problemset/problem/16/C
舒从 仂亠仆亳 从仂仂? 仂弍亠仄 仍舒亠 于 亰舒[fail]亳亠, 仗仂仂仄 仂: ∃仂亟仆亠 亟舒仆仆亠 舒亰仆亠 ∃亠舒仍亳亰舒亳 亢亠仍亠亰舒 舒亰仆舒 亠舒仍亳亰舒亳 舒仍亞仂亳仄舒 于从仍亳亟舒 仆舒 Python: def gcd(a,b): while a != b: if a > b: a = a - b else: b = b - a print(a)
舒从 仂亠仆亳 从仂仂? 仂弍亠仄 仍舒亠 于 亰舒[fail]亳亠, 仗仂仂仄 仂: ∃仂亟仆亠 亟舒仆仆亠 舒亰仆亠 ∃亠舒仍亳亰舒亳 亢亠仍亠亰舒 舒亰仆舒 弌从仂仂 于仗仂仍仆亠仆亳 仂仗亠亟亠仍仆仆仂亶 亳仆从亳亳 舒亰磲仆仂 舒亳亠从 亠从仂仆仂亠 从仂亠仆亳亠 于亳仍亠仆亳亶 .亟. 亳 .仗.
舒从 仂亠仆亳 从仂仂? 仂仍亠亠 仄舒亠仄舒亳亠从亳: -仆仂舒亳 O(g) - 仄仆仂亢亠于仂 仆从亳亶 f, 亟仍 从仂仂 亠于ﾑ 舒从亳亠 从仂仆舒仆 C 亳 N, 仂 |f(x)| C|g(x)| 亟仍 于亠 x > N. 舒仗亳 f = O(g) 亟仂仍仂于仆仂 仂弍仂亰仆舒舒亠, 仂 f 仗亳仆舒亟仍亠亢亳 仄仆仂亢亠于 O(g). 亳 仂仄 仂弍舒仆仂亠 于舒亢亠仆亳亠 O(g) = f 仆亠 亳仄亠亠 仄仍舒. 仂 亳, 仆舒舒 亰舒亟舒舒: 仂仗亳舒 仗仂于亠亟亠仆亳亠 仆从亳亳 于 亰舒于亳亳仄仂亳 仂 仗舒舒仄亠舒.
舒从 仂亠仆亳 从仂仂? 舒仄仂亳仄 舒仍亞仂亳仄 于亳仍亠仆亳 亰仆舒亠仆亳 仄仆仂亞仂仍亠仆舒 亠仗亠仆亳 n 于 亰舒亟舒仆仆仂亶 仂从亠 x. Pn(x) = anxn + an-1xn-1 + ... + aixi + ... + a1x + a0
舒从 仂亠仆亳 从仂仂? 舒仄仂亳仄 舒仍亞仂亳仄 于亳仍亠仆亳 亰仆舒亠仆亳 仄仆仂亞仂仍亠仆舒 亠仗亠仆亳 n 于 亰舒亟舒仆仆仂亶 仂从亠 x. Pn(x) = anxn + an-1xn-1 + ... + aixi + ... + a1x + a0 亳仍亠仆亳亠 i-亞仂 仍舒亞舒亠仄仂亞仂 (i=1..n) 亠弍亠 i 仄仆仂亢亠仆亳亶. 仆舒亳, 于亠亞仂 1 + 2 + 3 + ... + n =
舒从 仂亠仆亳 从仂仂? 舒仄仂亳仄 舒仍亞仂亳仄 于亳仍亠仆亳 亰仆舒亠仆亳 仄仆仂亞仂仍亠仆舒 亠仗亠仆亳 n 于 亰舒亟舒仆仆仂亶 仂从亠 x. Pn(x) = anxn + an-1xn-1 + ... + aixi + ... + a1x + a0 亳仍亠仆亳亠 i-亞仂 仍舒亞舒亠仄仂亞仂 (i=1..n) 亠弍亠 i 仄仆仂亢亠仆亳亶. 仆舒亳, 于亠亞仂 1 + 2 + 3 + ... + n = n(n+1)/2 仂仄亠 仂亞仂, 亠弍亠 n+1 仍仂亢亠仆亳亠.
舒从 仂亠仆亳 从仂仂? 舒仄仂亳仄 舒仍亞仂亳仄 于亳仍亠仆亳 亰仆舒亠仆亳 仄仆仂亞仂仍亠仆舒 亠仗亠仆亳 n 于 亰舒亟舒仆仆仂亶 仂从亠 x. Pn(x) = anxn + an-1xn-1 + ... + aixi + ... + a1x + a0 亳仍亠仆亳亠 i-亞仂 仍舒亞舒亠仄仂亞仂 (i=1..n) 亠弍亠 i 仄仆仂亢亠仆亳亶. 仆舒亳, 于亠亞仂 1 + 2 + 3 + ... + n = n(n+1)/2 仂仄亠 仂亞仂, 亠弍亠 n+1 仍仂亢亠仆亳亠. 亠亞仂 n(n+1)/2 + n + 1= n2/2 + 3n/2 + 1 仂仗亠舒亳亶.
舒从 仂亠仆亳 从仂仂? 舒从仂于仂 仗仂于亠亟亠仆亳亠 仆从亳亳? f(n)= n2/2 + 3n/2 + 1
舒从 仂亠仆亳 从仂仂? 舒从仂于仂 仗仂于亠亟亠仆亳亠 仆从亳亳? f(n)= n2/2 + 3n/2 + 1 仂于亠亟亠仆亳亠: O(n2) 仂仍仂亠 仂 仆 从于舒亟舒 亅仂 于亠仆 仂亠仆从舒, .亠 从仂仍亳亠于仂 仂仗亠舒亳亶 (舒 亰仆舒亳, 亳 于亠仄 舒弍仂) 舒亠 仆亠 弍亠亠, 亠仄 从于舒亟舒 从仂仍亳亠于舒 仍亠仄亠仆仂于. 丼仂弍 仗仂于于仂于舒, 仂 仂 舒从仂亠, 仗仂仄仂亳亠 仆舒 舒弍仍亳, 亞亟亠 仗亳于亠亟亠仆 亳仍舒, 亳仍仍ﾑ亳ﾑ亳亠 从仂仂 仂舒 亟仍 仆亠从仂仍从亳 舒亰仆 仆从亳亶.
舒从 仂亠仆亳 从仂仂? n log n n * log n n^2 1 0 0 1 16 4 64 256 256 8 2048 65536 4096 12 49152 16777216 65536 16 1048565 4294967296 1048576 20 20969520 1,0993E+12 16775616 24 402614784 2,81421E+14
舒从 仂亠仆亳 从仂仂? n log n n * log n n^2 1 0 0 1 16 4 64 256 256 8 2048 65536 4096 12 49152 16777216 65536 16 1048565 4294967296 1048576 20 20969520 1,0993E+12 16775616 24 402614784 2,81421E+14 仂仗亠舒亳 亟仍亳 3 仆 = 3*10-9 , 仂亞亟舒 亟仍 n =224 t = (2.81 * 1014) * (3 * 10-9) = 3 * 2.81 * 105 c ~ 10 亟仆亠亶
舒从 仂亠仆亳 从仂仂? 舒于亳仍舒 ∃亳 仂亠仆从亠 亰舒 仆从亳 弍亠亠 从仂仍亳亠于仂 仂仗亠舒亳亶, 于仂亰舒舒ﾑ亠亠 弍亠亠 于亠亞仂. ∃亳 仂亠仆从亠 O() 从仂仆舒仆 仆亠 亳于舒ﾑ.
亳仄亠 亳仂亢仂仗仂亳: 亠仂仄亠亳亠从仂亠 舒亰仄亳亠 ~28 Mpx (4800 x 6000 px) O(?)
亳仄亠 亳仂亢仂仗仂亳: 亠仂仄亠亳亠从仂亠 舒亰仄亳亠 ~28 Mpx (4800 x 6000 px) 弌仍仂亢仆仂 (N2 D2)
亳仄亠 亳仂亢仂仗仂亳: 亠仂仄亠亳亠从仂亠 舒亰仄亳亠
亳仄亠 亳仂亢仂仗仂亳: 亠仂仄亠亳亠从仂亠 舒亰仄亳亠 礆仂亶 仄亠仂亟: 457 亠从 亳弍仍. 仄亠仂亟: 31 亠从 亳弍仍. 仄亠仂亟: 3 亠从
亠 L-仆仂舒亳 http://ru.wikipedia.org/wiki/L-仆仂舒亳 L-仆仂舒亳 仂 舒亳仄仗仂亳亠从舒 仆仂舒亳, 舒仆舒仍仂亞亳仆舒 -仆仂舒亳亳, 亰舒仗亳于舒亠 从舒从 Ln[a,c] 亟仍 n 亠仄亳仄 从 弍亠从仂仆亠仆仂亳. 仂亟仂弍仆仂 O-弍仂仍仂仄, 仆仂舒亳 仂弍仆仂 亳仗仂仍亰亠 亟仍 亞弍仂亶 仂亠仆从亳 于亳仍亳亠仍仆仂亶 仍仂亢仆仂亳 仂仗亠亟亠仍亠仆仆仂亞仂 舒仍亞仂亳仄舒.

More Related Content

Algo 01 part01

  • 1. CV_RTF: algo posidelky 束亠仆从舒 仍仂亢仆仂亳 舒仍亞仂亳仄仂于損
  • 5. 舒从 仂亠仆亳 从仂仂? MatLAB 亠 仗亠亳舒仍仆亶 亳仆仄亠仆 仂亟: A = ones(500,500); B = ones(500,500) * 2; C = zeros(500,500); tic C = A .* B; toc % ====== tic for i = 1 : 500 for j = 1 : 500 C(i,j) = A(i, j) * B(i, j); end end toc
  • 6. 舒从 仂亠仆亳 从仂仂? MatLAB 亠 仗亠亳舒仍仆亶 亳仆仄亠仆 于仂亟: Elapsed time is 0.000822 seconds. Elapsed time is 0.008758 seconds.
  • 7. 舒从 仂亠仆亳 从仂仂? 弌++ 仄仂亢仆仂 仆舒仗亳舒 从仂仍! #include <ctime> clock_t time = clock(); // algorithm double delta = (double)(clock() time); delta /= CLOCKS_PER_SEC; cout << Time is << delta << endl;
  • 8. 舒从 仂亠仆亳 从仂仂? 仂弍亠仄 仍舒亠 于 亰舒[fail]亳亠, 仗仂仂仄 仂: ∃仂亟仆亠 亟舒仆仆亠 舒亰仆亠 ∃亠舒仍亳亰舒亳 亢亠仍亠亰舒 舒亰仆舒 仂仄仗舒仆亳 Reca 于仗从舒亠 仄仂仆亳仂, 弍仂仍仂亶 仗仂仗仍仆仂 仗仂仍亰亠 亳 仄仂亟亠仍 AB999 舒亰仄亠舒仄亳 从舒仆舒 ab 舒仆亳仄亠仂于. 亰-亰舒 仂仂弍亠仆仆仂亠亶 仗仂亳亰于仂亟于舒, 舒亰仄亠 从舒仆舒 于舒亢舒ﾑ 亠仍仄 亳仍仂仄 舒仆亳仄亠仂于. 亠亟舒于仆仂 于 仄仂亟 于仂仍仂 仂仂仆仂亠仆亳亠 仂仂仆 x:y. 仂仄仗舒仆亳 仂亠 仄亠仆亳 舒亰仄亠 从舒仆舒 于仂亠亞仂 仄仂仆亳仂舒 AB999 舒从, 仂弍 亠亞仂 仂仂仆仂亠仆亳亠 仂仂仆 舒仍仂 x:y, 仆仂 仗亳 仂仄 亠亞仂 仗仍仂舒亟 弍仍舒 仄舒从亳仄舒仍仆仂 于仂亰仄仂亢仆仂亶. 舒舒 亰舒亟舒舒 仂仗亠亟亠仍亳 舒亰仄亠 从舒仆舒 仄亠仆亠仆仆仂亶 仄仂亟亠仍亳, 亳仍亳 于仆亳, 仂 仂 亟亠仍舒 仆亠于仂亰仄仂亢仆仂. 仗亠于仂亶 仂从亠 于仂亟仆 亟舒仆仆 仂亟亠亢舒 4 亠仍 亳仍舒 a, b, x 亳 y (1a,b,x,y2揃109). http://codeforces.ru/problemset/problem/16/C
  • 9. 舒从 仂亠仆亳 从仂仂? 仂弍亠仄 仍舒亠 于 亰舒[fail]亳亠, 仗仂仂仄 仂: ∃仂亟仆亠 亟舒仆仆亠 舒亰仆亠 ∃亠舒仍亳亰舒亳 亢亠仍亠亰舒 舒亰仆舒 亠舒仍亳亰舒亳 舒仍亞仂亳仄舒 于从仍亳亟舒 仆舒 Python: def gcd(a,b): while a != b: if a > b: a = a - b else: b = b - a print(a)
  • 10. 舒从 仂亠仆亳 从仂仂? 仂弍亠仄 仍舒亠 于 亰舒[fail]亳亠, 仗仂仂仄 仂: ∃仂亟仆亠 亟舒仆仆亠 舒亰仆亠 ∃亠舒仍亳亰舒亳 亢亠仍亠亰舒 舒亰仆舒 弌从仂仂 于仗仂仍仆亠仆亳 仂仗亠亟亠仍仆仆仂亶 亳仆从亳亳 舒亰磲仆仂 舒亳亠从 亠从仂仆仂亠 从仂亠仆亳亠 于亳仍亠仆亳亶 .亟. 亳 .仗.
  • 11. 舒从 仂亠仆亳 从仂仂? 仂仍亠亠 仄舒亠仄舒亳亠从亳: -仆仂舒亳 O(g) - 仄仆仂亢亠于仂 仆从亳亶 f, 亟仍 从仂仂 亠于ﾑ 舒从亳亠 从仂仆舒仆 C 亳 N, 仂 |f(x)| C|g(x)| 亟仍 于亠 x > N. 舒仗亳 f = O(g) 亟仂仍仂于仆仂 仂弍仂亰仆舒舒亠, 仂 f 仗亳仆舒亟仍亠亢亳 仄仆仂亢亠于 O(g). 亳 仂仄 仂弍舒仆仂亠 于舒亢亠仆亳亠 O(g) = f 仆亠 亳仄亠亠 仄仍舒. 仂 亳, 仆舒舒 亰舒亟舒舒: 仂仗亳舒 仗仂于亠亟亠仆亳亠 仆从亳亳 于 亰舒于亳亳仄仂亳 仂 仗舒舒仄亠舒.
  • 12. 舒从 仂亠仆亳 从仂仂? 舒仄仂亳仄 舒仍亞仂亳仄 于亳仍亠仆亳 亰仆舒亠仆亳 仄仆仂亞仂仍亠仆舒 亠仗亠仆亳 n 于 亰舒亟舒仆仆仂亶 仂从亠 x. Pn(x) = anxn + an-1xn-1 + ... + aixi + ... + a1x + a0
  • 13. 舒从 仂亠仆亳 从仂仂? 舒仄仂亳仄 舒仍亞仂亳仄 于亳仍亠仆亳 亰仆舒亠仆亳 仄仆仂亞仂仍亠仆舒 亠仗亠仆亳 n 于 亰舒亟舒仆仆仂亶 仂从亠 x. Pn(x) = anxn + an-1xn-1 + ... + aixi + ... + a1x + a0 亳仍亠仆亳亠 i-亞仂 仍舒亞舒亠仄仂亞仂 (i=1..n) 亠弍亠 i 仄仆仂亢亠仆亳亶. 仆舒亳, 于亠亞仂 1 + 2 + 3 + ... + n =
  • 14. 舒从 仂亠仆亳 从仂仂? 舒仄仂亳仄 舒仍亞仂亳仄 于亳仍亠仆亳 亰仆舒亠仆亳 仄仆仂亞仂仍亠仆舒 亠仗亠仆亳 n 于 亰舒亟舒仆仆仂亶 仂从亠 x. Pn(x) = anxn + an-1xn-1 + ... + aixi + ... + a1x + a0 亳仍亠仆亳亠 i-亞仂 仍舒亞舒亠仄仂亞仂 (i=1..n) 亠弍亠 i 仄仆仂亢亠仆亳亶. 仆舒亳, 于亠亞仂 1 + 2 + 3 + ... + n = n(n+1)/2 仂仄亠 仂亞仂, 亠弍亠 n+1 仍仂亢亠仆亳亠.
  • 15. 舒从 仂亠仆亳 从仂仂? 舒仄仂亳仄 舒仍亞仂亳仄 于亳仍亠仆亳 亰仆舒亠仆亳 仄仆仂亞仂仍亠仆舒 亠仗亠仆亳 n 于 亰舒亟舒仆仆仂亶 仂从亠 x. Pn(x) = anxn + an-1xn-1 + ... + aixi + ... + a1x + a0 亳仍亠仆亳亠 i-亞仂 仍舒亞舒亠仄仂亞仂 (i=1..n) 亠弍亠 i 仄仆仂亢亠仆亳亶. 仆舒亳, 于亠亞仂 1 + 2 + 3 + ... + n = n(n+1)/2 仂仄亠 仂亞仂, 亠弍亠 n+1 仍仂亢亠仆亳亠. 亠亞仂 n(n+1)/2 + n + 1= n2/2 + 3n/2 + 1 仂仗亠舒亳亶.
  • 16. 舒从 仂亠仆亳 从仂仂? 舒从仂于仂 仗仂于亠亟亠仆亳亠 仆从亳亳? f(n)= n2/2 + 3n/2 + 1
  • 17. 舒从 仂亠仆亳 从仂仂? 舒从仂于仂 仗仂于亠亟亠仆亳亠 仆从亳亳? f(n)= n2/2 + 3n/2 + 1 仂于亠亟亠仆亳亠: O(n2) 仂仍仂亠 仂 仆 从于舒亟舒 亅仂 于亠仆 仂亠仆从舒, .亠 从仂仍亳亠于仂 仂仗亠舒亳亶 (舒 亰仆舒亳, 亳 于亠仄 舒弍仂) 舒亠 仆亠 弍亠亠, 亠仄 从于舒亟舒 从仂仍亳亠于舒 仍亠仄亠仆仂于. 丼仂弍 仗仂于于仂于舒, 仂 仂 舒从仂亠, 仗仂仄仂亳亠 仆舒 舒弍仍亳, 亞亟亠 仗亳于亠亟亠仆 亳仍舒, 亳仍仍ﾑ亳ﾑ亳亠 从仂仂 仂舒 亟仍 仆亠从仂仍从亳 舒亰仆 仆从亳亶.
  • 18. 舒从 仂亠仆亳 从仂仂? n log n n * log n n^2 1 0 0 1 16 4 64 256 256 8 2048 65536 4096 12 49152 16777216 65536 16 1048565 4294967296 1048576 20 20969520 1,0993E+12 16775616 24 402614784 2,81421E+14
  • 19. 舒从 仂亠仆亳 从仂仂? n log n n * log n n^2 1 0 0 1 16 4 64 256 256 8 2048 65536 4096 12 49152 16777216 65536 16 1048565 4294967296 1048576 20 20969520 1,0993E+12 16775616 24 402614784 2,81421E+14 仂仗亠舒亳 亟仍亳 3 仆 = 3*10-9 , 仂亞亟舒 亟仍 n =224 t = (2.81 * 1014) * (3 * 10-9) = 3 * 2.81 * 105 c ~ 10 亟仆亠亶
  • 20. 舒从 仂亠仆亳 从仂仂? 舒于亳仍舒 ∃亳 仂亠仆从亠 亰舒 仆从亳 弍亠亠 从仂仍亳亠于仂 仂仗亠舒亳亶, 于仂亰舒舒ﾑ亠亠 弍亠亠 于亠亞仂. ∃亳 仂亠仆从亠 O() 从仂仆舒仆 仆亠 亳于舒ﾑ.
  • 24. 亳仄亠 亳仂亢仂仗仂亳: 亠仂仄亠亳亠从仂亠 舒亰仄亳亠 礆仂亶 仄亠仂亟: 457 亠从 亳弍仍. 仄亠仂亟: 31 亠从 亳弍仍. 仄亠仂亟: 3 亠从
  • 25. 亠 L-仆仂舒亳 http://ru.wikipedia.org/wiki/L-仆仂舒亳 L-仆仂舒亳 仂 舒亳仄仗仂亳亠从舒 仆仂舒亳, 舒仆舒仍仂亞亳仆舒 -仆仂舒亳亳, 亰舒仗亳于舒亠 从舒从 Ln[a,c] 亟仍 n 亠仄亳仄 从 弍亠从仂仆亠仆仂亳. 仂亟仂弍仆仂 O-弍仂仍仂仄, 仆仂舒亳 仂弍仆仂 亳仗仂仍亰亠 亟仍 亞弍仂亶 仂亠仆从亳 于亳仍亳亠仍仆仂亶 仍仂亢仆仂亳 仂仗亠亟亠仍亠仆仆仂亞仂 舒仍亞仂亳仄舒.