-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathindex.html
934 lines (307 loc) · 34.5 KB
/
index.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
<!DOCTYPE html>
<html class="theme-next muse use-motion" lang="">
<head>
<meta charset="UTF-8"/>
<meta http-equiv="X-UA-Compatible" content="IE=edge" />
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=2"/>
<meta name="theme-color" content="#222">
<meta http-equiv="Cache-Control" content="no-transform" />
<meta http-equiv="Cache-Control" content="no-siteapp" />
<link href="/lib/font-awesome/css/font-awesome.min.css?v=4.6.2" rel="stylesheet" type="text/css" />
<link href="/css/main.css?v=6.0.6" rel="stylesheet" type="text/css" />
<link rel="apple-touch-icon" sizes="180x180" href="/images/apple-touch-icon-next.png?v=6.0.6">
<link rel="icon" type="image/png" sizes="32x32" href="/images/favicon-32x32-next.png?v=6.0.6">
<link rel="icon" type="image/png" sizes="16x16" href="/images/favicon-16x16-next.png?v=6.0.6">
<link rel="mask-icon" href="/images/logo.svg?v=6.0.6" color="#222">
<script type="text/javascript" id="hexo.configurations">
var NexT = window.NexT || {};
var CONFIG = {
root: '/',
scheme: 'Muse',
version: '6.0.6',
sidebar: {"position":"left","display":"post","offset":12,"b2t":false,"scrollpercent":false,"onmobile":false},
fancybox: false,
fastclick: false,
lazyload: false,
tabs: true,
motion: {"enable":true,"async":false,"transition":{"post_block":"fadeIn","post_header":"slideDownIn","post_body":"slideDownIn","coll_header":"slideLeftIn","sidebar":"slideUpIn"}},
algolia: {
applicationID: '',
apiKey: '',
indexName: '',
hits: {"per_page":10},
labels: {"input_placeholder":"Search for Posts","hits_empty":"We didn't find any results for the search: ${query}","hits_stats":"${hits} results found in ${time} ms"}
}
};
</script>
<meta property="og:type" content="website">
<meta property="og:title" content="tannotour">
<meta property="og:url" content="https://tannotour.github.io/index.html">
<meta property="og:site_name" content="tannotour">
<meta name="twitter:card" content="summary">
<meta name="twitter:title" content="tannotour">
<link rel="canonical" href="https://tannotour.github.io/"/>
<script type="text/javascript" id="page.configurations">
CONFIG.page = {
sidebar: "",
};
</script>
<title>tannotour</title>
<noscript>
<style type="text/css">
.use-motion .motion-element,
.use-motion .brand,
.use-motion .menu-item,
.sidebar-inner,
.use-motion .post-block,
.use-motion .pagination,
.use-motion .comments,
.use-motion .post-header,
.use-motion .post-body,
.use-motion .collection-title { opacity: initial; }
.use-motion .logo,
.use-motion .site-title,
.use-motion .site-subtitle {
opacity: initial;
top: initial;
}
.use-motion {
.logo-line-before i { left: initial; }
.logo-line-after i { right: initial; }
}
</style>
</noscript>
</head>
<body itemscope itemtype="http://schema.org/WebPage" lang="">
<div class="container sidebar-position-left
page-home">
<div class="headband">
<a href="https://github.com/tannotour"><img style="position: absolute; top: 0; right: 0; border: 0;" src="https://s3.amazonaws.com/github/ribbons/forkme_right_darkblue_121621.png" alt="Fork me on GitHub"></a>
</div>
<header id="header" class="header" itemscope itemtype="http://schema.org/WPHeader">
<div class="header-inner">
<div class="site-brand-wrapper">
<div class="site-meta ">
<div class="custom-logo-site-title">
<a href="/" class="brand" rel="start">
<span class="logo-line-before"><i></i></span>
<span class="site-title">tannotour</span>
<span class="logo-line-after"><i></i></span>
</a>
</div>
<p class="site-subtitle"></p>
</div>
<div class="site-nav-toggle">
<button aria-label="Toggle navigation bar">
<span class="btn-bar"></span>
<span class="btn-bar"></span>
<span class="btn-bar"></span>
</button>
</div>
</div>
<nav class="site-nav">
<ul id="menu" class="menu">
<li class="menu-item menu-item-home">
<a href="/" rel="section">
<i class="menu-item-icon fa fa-fw fa-home"></i> <br />Home</a>
</li>
<li class="menu-item menu-item-archives">
<a href="/archives/" rel="section">
<i class="menu-item-icon fa fa-fw fa-archive"></i> <br />Archives</a>
</li>
</ul>
</nav>
</div>
</header>
<main id="main" class="main">
<div class="main-inner">
<div class="content-wrap">
<div id="content" class="content">
<section id="posts" class="posts-expand">
<article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
<div class="post-block">
<link itemprop="mainEntityOfPage" href="https://tannotour.github.io/2018/09/15/数组-旋转数组/">
<span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
<meta itemprop="name" content="tannotour">
<meta itemprop="description" content="">
<meta itemprop="image" content="http://ojd6d6k74.bkt.clouddn.com/header.jpg">
</span>
<span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
<meta itemprop="name" content="tannotour">
</span>
<header class="post-header">
<h1 class="post-title" itemprop="name headline">
<a class="post-title-link" href="/2018/09/15/数组-旋转数组/" itemprop="url">旋转数组</a></h1>
<div class="post-meta">
<span class="post-time">
<span class="post-meta-item-icon">
<i class="fa fa-calendar-o"></i>
</span>
<span class="post-meta-item-text">Posted on</span>
<time title="Post created" itemprop="dateCreated datePublished" datetime="2018-09-15T23:25:38+08:00">2018-09-15</time>
</span>
</div>
</header>
<div class="post-body" itemprop="articleBody">
<h2 id="概述"><a href="#概述" class="headerlink" title="概述"></a>概述</h2><p>还有两年毕业，需要准备下算法知识了，从leetcode上总结的题目以及解题思路，与大家分享，共同进步。</p>
<h2 id="题目描述"><a href="#题目描述" class="headerlink" title="题目描述"></a>题目描述</h2><p>给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。</p>
<h3 id="示例1"><a href="#示例1" class="headerlink" title="示例1"></a>示例1</h3><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br></pre></td><td class="code"><pre><span class="line">输入: [1,2,3,4,5,6,7] 和 k = 3</span><br><span class="line">输出: [5,6,7,1,2,3,4]</span><br><span class="line">解释:</span><br><span class="line">向右旋转 1 步: [7,1,2,3,4,5,6]</span><br><span class="line">向右旋转 2 步: [6,7,1,2,3,4,5]</span><br><span class="line">向右旋转 3 步: [5,6,7,1,2,3,4]</span><br></pre></td></tr></table></figure>
<h3 id="示例2"><a href="#示例2" class="headerlink" title="示例2"></a>示例2</h3><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br></pre></td><td class="code"><pre><span class="line">输入: [-1,-100,3,99] 和 k = 2</span><br><span class="line">输出: [3,99,-1,-100]</span><br><span class="line">解释: </span><br><span class="line">向右旋转 1 步: [99,-1,-100,3]</span><br><span class="line">向右旋转 2 步: [3,99,-1,-100]</span><br></pre></td></tr></table></figure>
<h3 id="说明"><a href="#说明" class="headerlink" title="说明"></a>说明</h3><p>尽可能想出更多的解决方案，至少有三种不同的方法可以解决这个问题。<br>要求使用空间复杂度为 O(1) 的原地算法。</p>
<h2 id="解题思路"><a href="#解题思路" class="headerlink" title="解题思路"></a>解题思路</h2><h3 id="分析"><a href="#分析" class="headerlink" title="分析"></a>分析</h3><p>首先，我们分析一下题目：<br>输入是一个数组nums和一个整数k，我们需要做的就是将这个数组往右移k位，第n-1位覆盖第n位上的数组，最后一位补到下标为0的位置上；<br>这个题目让我想到了以前学过的二进制循环移位器，其实是一样的，现在需要我们自己来实现一个简单的循环移位器了；<br>大体思路就是每次只往右移一位，直到移动了k次为止。<br>下面为代码实现，代码是kotlin编写的。</p>
<h3 id="具体实现"><a href="#具体实现" class="headerlink" title="具体实现"></a>具体实现</h3><figure class="highlight kotlin"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Solution</span> </span>{</span><br><span class="line"> <span class="function"><span class="keyword">fun</span> <span class="title">rotate</span><span class="params">(nums: <span class="type">IntArray</span>, k: <span class="type">Int</span>)</span></span>: <span class="built_in">Unit</span> {</span><br><span class="line"> <span class="keyword">for</span>(i <span class="keyword">in</span> <span class="number">0</span> until k){</span><br><span class="line"> <span class="keyword">val</span> last = nums.last()</span><br><span class="line"> <span class="keyword">for</span>(index <span class="keyword">in</span> nums.size<span class="number">-1</span> downTo <span class="number">1</span>){</span><br><span class="line"> nums[index] = nums[index<span class="number">-1</span>]</span><br><span class="line"> }</span><br><span class="line"> nums[<span class="number">0</span>] = last</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
</div>
<footer class="post-footer">
<div class="post-eof"></div>
</footer>
</div>
</article>
<article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
<div class="post-block">
<link itemprop="mainEntityOfPage" href="https://tannotour.github.io/2018/09/02/数组-从排序数组中删除重复项/">
<span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
<meta itemprop="name" content="tannotour">
<meta itemprop="description" content="">
<meta itemprop="image" content="http://ojd6d6k74.bkt.clouddn.com/header.jpg">
</span>
<span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
<meta itemprop="name" content="tannotour">
</span>
<header class="post-header">
<h1 class="post-title" itemprop="name headline">
<a class="post-title-link" href="/2018/09/02/数组-从排序数组中删除重复项/" itemprop="url">从排序数组中删除重复元素</a></h1>
<div class="post-meta">
<span class="post-time">
<span class="post-meta-item-icon">
<i class="fa fa-calendar-o"></i>
</span>
<span class="post-meta-item-text">Posted on</span>
<time title="Post created" itemprop="dateCreated datePublished" datetime="2018-09-02T10:19:01+08:00">2018-09-02</time>
</span>
</div>
</header>
<div class="post-body" itemprop="articleBody">
<h2 id="概述"><a href="#概述" class="headerlink" title="概述"></a>概述</h2><p>还有两年毕业，需要准备下算法知识了，这篇以及后面的文章为leetcode上总结的题目以及解题思路，与大家分享，共同进步。</p>
<h2 id="题目描述"><a href="#题目描述" class="headerlink" title="题目描述"></a>题目描述</h2><p>给定一个排序数组，需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。<br>不要使用额外的数组空间，必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。</p>
<h3 id="示例1"><a href="#示例1" class="headerlink" title="示例1"></a>示例1</h3><p>给定数组 nums = [1,1,2],<br>函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。<br>不需要考虑数组中超出新长度后面的元素。</p>
<h3 id="示例2"><a href="#示例2" class="headerlink" title="示例2"></a>示例2</h3><p>给定 nums = [0,0,1,1,1,2,2,3,3,4],<br>函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。<br>不需要考虑数组中超出新长度后面的元素。</p>
<h3 id="说明"><a href="#说明" class="headerlink" title="说明"></a>说明</h3><p>为什么返回数值是整数，但输出的答案是数组呢?<br>请注意，输入数组是以“引用”方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。<br>你可以想象内部操作如下:<br><figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line">// nums 是以“引用”方式传递的。也就是说，不对实参做任何拷贝</span><br><span class="line">int len = removeDuplicates(nums);</span><br><span class="line">// 在函数里修改输入数组对于调用者是可见的。</span><br><span class="line">// 根据函数返回的长度, 它会打印出数组中该长度范围内的所有元素。</span><br><span class="line">for (int i = 0; i < len; i++) {</span><br><span class="line"> print(nums[i]);</span><br><span class="line">}</span><br></pre></td></tr></table></figure></p>
<h2 id="解题思路"><a href="#解题思路" class="headerlink" title="解题思路"></a>解题思路</h2><h3 id="分析"><a href="#分析" class="headerlink" title="分析"></a>分析</h3><p>首先，我们分析一下题目：<br>题目中提到输入是一个数组，并且这个数组是有序的；<br>只需要将重复元素删掉，后面的元素补上来即可；<br>返回不重复元素的个数。<br>根据以上题目分析，我们要至少遍历数组一次，在遍历过程中，需要知道是从哪个元素开始重复的，那么就可以使用一个变量 preValuel 来存储上一个元素的值，通过 nums[i] != preValue 判断当前元素是否与上一个元素重复，如果不重复的话就将计数加一并更新原数组以及变量 preValue 。<br>好了，思路大概就是上面所述，可能有些抽象或者是我表述的不是很清晰，那么看下下面的代码实现，代码是kotlin编写的。</p>
<h3 id="具体实现"><a href="#具体实现" class="headerlink" title="具体实现"></a>具体实现</h3><figure class="highlight kotlin"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br></pre></td><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Solution</span> </span>{</span><br><span class="line"> <span class="function"><span class="keyword">fun</span> <span class="title">removeDuplicates</span><span class="params">(nums: <span class="type">IntArray</span>)</span></span>: <span class="built_in">Int</span> {</span><br><span class="line"> <span class="keyword">if</span>(nums.isEmpty()) <span class="keyword">return</span> <span class="number">0</span></span><br><span class="line"> <span class="keyword">var</span> result = <span class="number">1</span></span><br><span class="line"> <span class="keyword">var</span> preValue = nums[<span class="number">0</span>]</span><br><span class="line"> <span class="keyword">for</span>(i <span class="keyword">in</span> <span class="number">1</span> until nums.size){</span><br><span class="line"> <span class="keyword">if</span>(nums[i] != preValue){</span><br><span class="line"> nums[result] = nums[i]</span><br><span class="line"> preValue = nums[i]</span><br><span class="line"> result ++</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">return</span> result</span><br><span class="line"> }</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
</div>
<footer class="post-footer">
<div class="post-eof"></div>
</footer>
</div>
</article>
<article class="post post-type-normal" itemscope itemtype="http://schema.org/Article">
<div class="post-block">
<link itemprop="mainEntityOfPage" href="https://tannotour.github.io/2018/04/19/算法学习-1/">
<span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
<meta itemprop="name" content="tannotour">
<meta itemprop="description" content="">
<meta itemprop="image" content="http://ojd6d6k74.bkt.clouddn.com/header.jpg">
</span>
<span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
<meta itemprop="name" content="tannotour">
</span>
<header class="post-header">
<h1 class="post-title" itemprop="name headline">
<a class="post-title-link" href="/2018/04/19/算法学习-1/" itemprop="url">'算法学习笔记-1'</a></h1>
<div class="post-meta">
<span class="post-time">
<span class="post-meta-item-icon">
<i class="fa fa-calendar-o"></i>
</span>
<span class="post-meta-item-text">Posted on</span>
<time title="Post created" itemprop="dateCreated datePublished" datetime="2018-04-19T23:31:01+08:00">2018-04-19</time>
</span>
</div>
</header>
<div class="post-body" itemprop="articleBody">
<h2 id="概述"><a href="#概述" class="headerlink" title="概述"></a>概述</h2><h3 id="算法"><a href="#算法" class="headerlink" title="算法"></a>算法</h3><p>算法是解决特定问题的方法与过程，是指令的有序序列。<br>严格地说，算法具有以下几点特性：<br><strong>输入</strong>：有外部变量作为算法的输入。当然，也可以没有外部变量，但是一般情况下，算法都有外部变量作为输入。<br><strong>输出</strong>：算法至少有一个输出，输出可以是函数的返回结果，也可以是对文件的修改抑或是对某个接口的访问<br><strong>确定性</strong>：组成算法的每条指令要求必须无歧义。<br><strong>有限性</strong>：算法要能在有限时间内执行完毕。</p>
<h3 id="程序"><a href="#程序" class="headerlink" title="程序"></a>程序</h3><p>程序是算法的具体实现</p>
<h3 id="算法复杂度"><a href="#算法复杂度" class="headerlink" title="算法复杂度"></a>算法复杂度</h3><h4 id="时间频度"><a href="#时间频度" class="headerlink" title="时间频度"></a><a href="https://blog.csdn.net/itachi85/article/details/54882603" title="时间频度" target="_blank" rel="noopener">时间频度</a></h4><p>一个算法执行所耗费的时间，从理论上是不能算出来的，必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试，只需知道哪个算法花费的时间多，哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。</p>
<h4 id="时间复杂度T-T-n"><a href="#时间复杂度T-T-n" class="headerlink" title="时间复杂度T=T(n)"></a><a href="https://blog.csdn.net/itachi85/article/details/54882603" title="T=T(n)" target="_blank" rel="noopener">时间复杂度T=T(n)</a></h4><p>前面提到的时间频度T(n)中，n称为问题的规模，当n不断变化时，时间频度T(n)也会不断变化。但有时我们想知道它变化时呈现什么规律，为此我们引入时间复杂度的概念。一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n)，使得当n趋近于无穷大时，T（n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数，记作T(n)=O(f(n))，它称为算法的渐进时间复杂度，简称时间复杂度。</p>
<h4 id="空间复杂度S-S-n"><a href="#空间复杂度S-S-n" class="headerlink" title="空间复杂度S=S(n)"></a>空间复杂度S=S(n)</h4><p>算法的空间复杂度指的是：算法运行过程中，<font color="red" size="5">辅助空间</font>的大小，而不是指算法运行时实际占用的空间，与算法规模没有关系。</p>
<h4 id="大O表示法"><a href="#大O表示法" class="headerlink" title="大O表示法"></a>大O表示法</h4><p>我的理解就是，只取式子中对最终结果影响最大的项，其余项忽略不计。<br>例如：</p>
<table><tr><td>表达式</td><td>大O表示法</td></tr><tr><td>2</td><td>O(1)</td></tr><tr><td>10n</td><td>O(n)</td></tr><tr><td>10n²</td><td>O(n²)</td></tr><tr><td>10n³+20n²+30n+40</td><td>O(n³)</td></tr></table><br>下面给出常见的时间复杂度(从上往下，算法时间复杂度越来越高)：<br><table><tr><td>常数阶</td><td>O(1)</td></tr><tr><td>对数阶</td><td>O(logn)</td></tr><tr><td>线性阶</td><td>O(n)</td></tr><tr><td>线性对数阶</td><td>O(nlogn)</td></tr><tr><td>多项式阶</td><td>O(n²)、O(n³)等</td></tr><tr><td>指数阶</td><td>O(2^n)、O(n!)、O(n^n)</td></tr></table>
<h3 id="算法复杂度分析方法"><a href="#算法复杂度分析方法" class="headerlink" title="算法复杂度分析方法"></a>算法复杂度分析方法</h3><h4 id="计算模型"><a href="#计算模型" class="headerlink" title="计算模型"></a>计算模型</h4><p>我们只考虑在单处理及单线程的情况下（即不考虑并行）算法执行的复杂度，下面用时复杂度举例说明。<br>例如<br>对于以下kotlin代码：<br><figure class="highlight kotlin"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">var</span> x = <span class="number">0</span>;</span><br><span class="line"><span class="keyword">for</span>(i <span class="keyword">in</span> <span class="number">1.</span>.n){</span><br><span class="line"> x += <span class="number">1</span>;</span><br><span class="line">}</span><br></pre></td></tr></table></figure></p>
<p>不难看出，上述代码中 x += 1 执行了n次，因此，时间复杂度为<font color="blue">O(n)</font>。<br>对于以下kotlin代码：<br><figure class="highlight kotlin"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">var</span> x = <span class="number">0</span>;</span><br><span class="line"><span class="keyword">for</span>(i <span class="keyword">in</span> <span class="number">1.</span>.n){</span><br><span class="line"> <span class="keyword">for</span>(j <span class="keyword">in</span> <span class="number">1.</span>.n){</span><br><span class="line"> x += <span class="number">1</span>;</span><br><span class="line"> }</span><br><span class="line">}</span><br></pre></td></tr></table></figure></p>
<p>不难看出，上述代码中 x += 1 执行了n²次，因此，时间复杂度为<font color="blue">O(n²)</font>。<br>对于以下kotlin代码：<br><figure class="highlight kotlin"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">fun</span> <span class="title">matrixMat</span><span class="params">(matrixOne: <span class="type">Array</span><<span class="type">Array</span><<span class="type">Int</span>>>, matrixTwo: <span class="type">Array</span><<span class="type">Array</span><<span class="type">Int</span>>>)</span></span>: Array<Array<<span class="built_in">Int</span>>>{</span><br><span class="line"> <span class="keyword">if</span>(matrixOne.isEmpty() && matrixTwo.isEmpty()){</span><br><span class="line"> <span class="keyword">return</span> Array(<span class="number">1</span>, {Array(<span class="number">1</span>){<span class="number">0</span>}})</span><br><span class="line"> }<span class="keyword">else</span> <span class="keyword">if</span>(matrixOne.isEmpty()){</span><br><span class="line"> <span class="keyword">throw</span> RuntimeException(<span class="string">"matrixOne is empty."</span>)</span><br><span class="line"> }<span class="keyword">else</span> <span class="keyword">if</span>(matrixTwo.isEmpty()){</span><br><span class="line"> <span class="keyword">throw</span> RuntimeException(<span class="string">"matrixTwo is empty."</span>)</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">val</span> rowOne = matrixOne.size</span><br><span class="line"> <span class="keyword">val</span> colOne = matrixOne.first().size</span><br><span class="line"> <span class="keyword">val</span> rowTwo = matrixTwo.size</span><br><span class="line"> <span class="keyword">val</span> colTwo = matrixTwo.first().size</span><br><span class="line"> <span class="keyword">if</span>(colOne != rowTwo){</span><br><span class="line"> <span class="keyword">throw</span> RuntimeException(<span class="string">"the col of matrixOne is not equal to the row of matrixTwo."</span>)</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">val</span> result = Array(matrixOne.size, {Array(matrixTwo.first().size){<span class="number">0</span>}})</span><br><span class="line"> <span class="keyword">for</span>(i <span class="keyword">in</span> <span class="number">0</span> until rowOne){</span><br><span class="line"> <span class="keyword">for</span> (j <span class="keyword">in</span> <span class="number">0</span> until colTwo){</span><br><span class="line"> <span class="keyword">for</span>(k <span class="keyword">in</span> <span class="number">0</span> until colOne){</span><br><span class="line"> result[i][j] += matrixOne[i][k] * matrixTwo[k][j]</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">return</span> result</span><br><span class="line"> }</span><br></pre></td></tr></table></figure></p>
<p>上述代码实现了两个整型矩阵相乘，重点在最后的三个for循环嵌套部分，它前面是对输入参数合理性检查。<br>不难看出，上述代码中 result[i][j] += matrixOne[i][k] * matrixTwo[k][j] 执行了n³次，用大O表示法表示，时间复杂度为<font color="blue">O(n³)</font>。</p>
</div>
<footer class="post-footer">
<div class="post-eof"></div>
</footer>
</div>
</article>
</section>
</div>
</div>
<div class="sidebar-toggle">
<div class="sidebar-toggle-line-wrap">
<span class="sidebar-toggle-line sidebar-toggle-line-first"></span>
<span class="sidebar-toggle-line sidebar-toggle-line-middle"></span>
<span class="sidebar-toggle-line sidebar-toggle-line-last"></span>
</div>
</div>
<aside id="sidebar" class="sidebar">
<div class="sidebar-inner">
<section class="site-overview-wrap sidebar-panel sidebar-panel-active">
<div class="site-overview">
<div class="site-author motion-element" itemprop="author" itemscope itemtype="http://schema.org/Person">
<img class="site-author-image" itemprop="image"
src="http://ojd6d6k74.bkt.clouddn.com/header.jpg"
alt="tannotour" />
<p class="site-author-name" itemprop="name">tannotour</p>
<p class="site-description motion-element" itemprop="description"></p>
</div>
<nav class="site-state motion-element">
<div class="site-state-item site-state-posts">
<a href="/archives/">
<span class="site-state-item-count">3</span>
<span class="site-state-item-name">posts</span>
</a>
</div>
<div class="site-state-item site-state-tags">
<span class="site-state-item-count">2</span>
<span class="site-state-item-name">tags</span>
</div>
</nav>
</div>
</section>
</div>
</aside>
</div>
</main>
<footer id="footer" class="footer">
<div class="footer-inner">
<div class="copyright">© <span itemprop="copyrightYear">2018</span>
<span class="with-love" id="animate">
<i class="fa fa-user"></i>
</span>
<span class="author" itemprop="copyrightHolder">tannotour</span>
</div>
<div class="powered-by">Powered by <a class="theme-link" target="_blank" href="https://hexo.io">Hexo</a></div>
<span class="post-meta-divider">|</span>
<div class="theme-info">Theme — <a class="theme-link" target="_blank" href="https://github.com/theme-next/hexo-theme-next">NexT.Muse</a> v6.0.6</div>
</div>
</footer>
<div class="back-to-top">
<i class="fa fa-arrow-up"></i>
</div>
</div>
<script type="text/javascript">
if (Object.prototype.toString.call(window.Promise) !== '[object Function]') {
window.Promise = null;
}
</script>
<script type="text/javascript" src="/lib/jquery/index.js?v=2.1.3"></script>
<script type="text/javascript" src="/lib/velocity/velocity.min.js?v=1.2.1"></script>
<script type="text/javascript" src="/lib/velocity/velocity.ui.min.js?v=1.2.1"></script>
<script type="text/javascript" src="/js/src/utils.js?v=6.0.6"></script>
<script type="text/javascript" src="/js/src/motion.js?v=6.0.6"></script>
<script type="text/javascript" src="/js/src/bootstrap.js?v=6.0.6"></script>
</body>
</html>